1
Construct TM to check well formed mess of parenthesis.

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: May2015

1
1
  1. We can solve this problem with PDA as well as with TM also.

  2. The parenthesis should be well formed in case of expression solving.

  3. The logic which will apply which will apply will be very much similar to the logic for finding equal number of a’s and equal number of b’s.

  4. We will start moving towards right, when we get any ‘)’ we will mark it as * and move left in search of ‘(’. Mark it as *. Thus we will repeated this process for the complete input string.

  5. For example:

enter image description here

  1. The TM will look like this-

enter image description here

  1. The transition table for this TM will be:

enter image description here

1
Please log in to add an answer.

Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more