Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: May2015

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:

1. The TM will look like this-

1. The transition table for this TM will be: