9. Pushdown Automata

Feb 3, 2022

• similar to finite automata but with added stack

  • input tape moves left to right, cannot go backwards
  • infinite stack for pushing and popping symbols
  • stack may have initial stack symbol to identify bottom of stack

• in notation \(a, b \rightarrow c\)   \(a\) is input symbol, \(b\) pop symbol, \(c\) push symbol

  • (when \(a, b \neq \epsilon\)) to follow this transition \(a\) must be next on input tape and \(b\) on top of stack

• transitions containing \(\epsilon\)

  • \(a, \epsilon \rightarrow \epsilon\) - process input symbol, stack remains unmodified
  • \(a, b \rightarrow \epsilon\) - process input symbol, pop topmost stack symbol, nothing pushed
  • \(\epsilon, b \rightarrow c\) - \(\epsilon\)-transition, no input tape symbol is processed, pop and push stack

• PDAs are nondeterministic and multiple transitions may be allowed

• to accept a state: all input must be consumed and last state is an accept state

  • the final content of stack does not matter