Pushdown Automata
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.
A stack does two operations −- Push − a new symbol is added at the top.
- Pop − the top symbol is read and removed.
Push − a new symbol is added at the top.
Pop − the top symbol is read and removed.
Pushdown Automata
- A pushdown automaton (PDA) is a finite automaton equipped with a stack-based memory.
- Each transition
- is based on the current input symbol and the top of the stack,
- optionally pops the top of the stack, and
- optionally pushes new symbols onto the stack.
- Initially, the stack holds a special symbol Z0 that indicates the bottom of the stack.
Our First PDA
- Consider the language L = { w ∈ Σ* | w is a string of balanced digits } over Σ = { 0, 1 }
- We can exploit the stack to our advantage:
- Whenever we see a 0, push it onto the stack.
- Whenever we see a 1, pop the corresponding 0 from the stack (or fail if not matched)
- When input is consumed, if the stack is empty, accept.
Post a Comment