Design a pushdown automaton which accepts a string of alphabet parenthesis.

Matching parenthesis using the stack:

·     An automaton can use the stack to recognize balanced parenthesis

·     e.g. (()) () is balanced, but (()) () and (()) are not balanced

o   On seeing a (push it on the stack

o   On seeing a ) pop a (from the stack

o   If attempt to pop an empty stack, reject

o   If stack no empty at the end, reject

o   Else accept

Figure: Matching parenthesis – PDA construction

·     First push a “bottom-of-the stack” symbol $ and move to q.

·     On seeing a (push it onto the stack

·     On seeing a ) pop if a (is in the stack

·   pop $ and move to final state  q_f.