<aside> 🥞 A finite automaton + a stack = a push down automaton.

</aside>

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

• $Q$ is a set of states
• $\Sigma$ is the input alphabet
• $\Gamma$ is the stack alphabet
  • Includes $\Sigma$ and usually $ to denote the empty stack
• $\delta: Q \times \Sigma_\epsilon \times \Gamma_\epsilon \rightarrow 2^{(Q \times \Gamma_\epsilon)}$
  • The third argument corresponds to what the machine ‘pops’ from the stack
• $q_0 \in Q$, the start state
• $F \subseteq Q$, the final states

<aside> 😋 By default, PDA are non-deterministic.

</aside>

Graphical notation

We label our transitions differently:

We always

• Read a letter
• Pop a letter
• Push a letter

Any of these can be $\epsilon$.

If $a$ is not being read, or $c$ is not the top element of the stack, then the transition cannot be taken.

<aside> 🧬 We can more generally write $a,c \rightarrow w$ where $w \in \Sigma^*$. For example, $a,c \rightarrow milk$ will read $a$, pop $c$, and add $m-i-l-k$ to the stack such that $m$ ends up on top.

</aside>