What is PDA?

A pushdown automaton is a way to implement a context-free grammar in a similar way we design DFA for a regular grammar. A DFA can remember a finite amount of information, but a PDA can remember an infinite amount of information.

PDA Examples

{x ∈ {a,b,c}* : x = wcwR for w ∈ {a,b}*} The machine pushes a's and b's in state s, makes a transition to f when it sees the middle marker, c, and then matches input symbols with those on the stack and pops the stack symbol. Non-accepting string examples are these: ε in state s ab in state s with non-empty stack abcab in state f with unconsumed input and non-empty stack abcb in state f with non-empty stack abcbab in state f with unconsumed input and empty stack Observe that this PDA is deterministic in the sense that there are no choices in transitions.

Practice

Push-down automaton for unary addition
Rules: S → aSa | +aEa
E → aEa | =