1
19kviews
Construct TM to check well formed mess of parenthesis.
written 7.7 years ago by | • modified 7.7 years ago |
Mumbai university > Comp > SEM 4 > TCS
Marks: 10M
Year: May2015
ADD COMMENT
EDIT
1 Answer
written 7.7 years ago by | • modified 7.7 years ago |
Mumbai university > Comp > SEM 4 > TCS
Marks: 10M
Year: May2015
written 7.7 years ago by |
We can solve this problem with PDA as well as with TM also.
The parenthesis should be well formed in case of expression solving.
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.
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.
For example: