Pushdown Automaton

Lecture 9

Every pushdown automaton accepts a context-free-language and vice versa.

Essentially an NFA with a stack

• In every state, a PDA has as input: top of stack and input character, and can push/pop the stack and go to another state.

• Note that PDA = NFA w/ stack and DPDA = DFA w/ stack

• PDA is more powerful than DPDA

  • Note that we cannot do the powerset construction (which can convert NFAs to DFAs) since the stack has unbounded size

Example $\{0^n\#1^n|n\ge0\}$

• Sketch

  • push 0 to stack until we see #

  • then, pop $0$ from stack whenever we consume $1$

  • accept when stack is empty

definition

• $M=(Q,\Sigma,\Gamma,\delta,q_0,F)$ where

  • $Q$ is the set of states

  • $\Sigma$ is the input alphabet

  • $\Gamma$ is the stack alphabet

  • $\delta:Q\times\Sigma_\epsilon\times\Gamma_\epsilon→2^{Q\times\Gamma_\epsilon}$ is the transition function

    • $\Sigma_\epsilon\coloneqq\Sigma\cup\{\epsilon\}$ and $\Gamma_\epsilon\coloneqq\Gamma\cup\{\epsilon\}$

    • For a PDA in state $p$, seeing input $a$ with ToS $d$, move to state $

    • TODO

  • $q_0\in Q$ is the initial state

  • $F\subseteq Q$ are the accepting states