Formal Definition

Basically, a PDA is an NFA with a stack; formally we define a PDA as consisting of:

• An alphabet $\Sigma$ of input symbols
• A set of states, of which we distinguish:
  • a unique start state
  • a set of final states
• An alphabet $\Gamma$ of stack symbols
• A transition relation which, for any given state, input symbol and stack symbol, gives a new state and stack symbol; i.e. it has the form:
  
  $$(State,\, InputSymbol,\, StackSymbol) \;\mapsto\; (State,\,StackSymbol)$$
  
  

Basically, if $a \in \Sigma$, $t,u \in \Gamma$ and $P$ and $Q$ are states, a transition of the form

$$(P,a,t) \mapsto (Q,u)$$

means ``read the symbol $\hbox{\lq }{a}\hbox{'}$ from the input, move from state $P$ to state $Q$, and replace the symbol $t$ on top of the stack with the symbol $u$''.

Obviously for this to happen we must be in state $P$, we must have $\hbox{\lq }{a}\hbox{'}$ as the next symbol on the input tape, and $t$ must be on top of the stack.

The actions push and pop are instances of the above transitions; for any stack symbol $t$, we have

• push $t$ is $(P,\varepsilon,\varepsilon) \mapsto (Q,t)$
• pop $t$ is $(P,\varepsilon,t) \mapsto (Q,\varepsilon)$

A PDA is said to accept some string $x$ if and only if we can get:

-

from the start state with an empty stack and $x$ as input

-

to a finish state with an empty stack and an empty input.