Pushdown Automata

def. Pushdown Autotmaton (PDA)

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

Where:

• $\Gamma$: stack alphabet
• $z$: stack bottom market
• $\delta$ is a transition function where for $q,q^{\prime }\in Q,\sigma \in \Sigma ,\gamma \in \Gamma$

$$(q,\sigma ,\gamma )\mapsto \{(q^{\prime },{\gamma }^{\ast }),...\}$$

…where the destination set is a finite set.

…and strings can be accepted by either final state xor an empty stack (equivalent)

We’re going to deal mostly with nondeterministic pushdown automata (NPDA), as they are more useful.

Described mechanically:

1. Input tape is read only once, left to right
2. A read head has finite number of states
3. A read head has a stack from which the top letter can be read off

def. the current Configuration of a PDA is described as a tuple

$$(q,a\mathbf{w},b\mathbf{x})⊢(q^{\prime },w,x)$$

where $⊢$ represents a single step of a PDA.

final state or an empty stack; these two definitions are equivalent.