Automata turing machine for balanced parenthesis

Create the Turing Machine for the following languages to print yes at the start of the tape if valid string and to print no at the start if not valid. Alphabet s is printed as the first character on input tape to indicate the start of the string. In simple words you need to design a turing machine for balanced parenthesis.

Language of braces
Language of the correctly nested braces e.g.
Valid string: [ [ [ ] [ ] ] [ ] ]
Invalid String [ ] ] [ [ ]

turing machine for balanced parenthesis

Automata turing machine for balanced parenthesis

Design an Input/Output turing machine that checks well formed string of parenthesis.

Example:

((( )( ))( )) -> Valid

( )( ))( ) -> Invalid

Logic:

Step 1: Move right for every opening bracket in the beginning.

Step 2: Once you find a closing bracket, put X in place of it.

Step 3: When you put X in place of any closing bracket, move right and search for its opening bracket. When you find its opening, place X in place of it.

Accepting Criteria:

  • You will be moving left for searching new opening parenthesis bracket and you found ‘Λ’.
  • Start moving left and this you should not find anything remaining except X. Move until you reach at the beginning.
  • Once you reach at start, put Y as acceptance sign.

Rejecting Criteria:

  • You have found stating bracket but may not found its closing bracket and you reach at the end. i.e. got ‘Λ’.
  • You are moving left for new opening and you reach end, you are coming back to starting and you find some (one or more) closing brackets.

Result:

  • For accepting criteria, you must need to reach ‘start’ with no closing bracket remaining.

Watch Video Simulation for balanced parenthesis turing machine

 

Watch Solution

Related posts