12. Pushdown Automata

13/03/23

.......

How does PDA Work?

$PDA P = (Q,\Sigma)$

• $Q$ - Finite set of states $Q=\{q_0,q_1,q_2\}$
• $\Sigma$ - the alphabet (finite set) $\Sigma=\{a,b\}$
• $\Gamma$ - stack alphabet (finite set) $\Gamma= \{a,b,\# \}$

$S:Q \to\Sigma\to\Gamma\to\Gamma^*\to Q\to Prop$

How to run a PDA?

Instantaneous Description