structural:scholar_edition
Example

The following is the formal description of the PDA which recognizes the language { 0 n 1 n ∣ n ≥ 0 } {\displaystyle \{0^{n}1^{n}\mid n\geq 0\}} by final state:

M = (Q, Σ, Γ, δ, q 0, Z, F) {\displaystyle M=(Q,\ \Sigma,\ \Gamma,\ \delta,\ q_{0},\ Z,\ F)}, where

The transition relation δ {\displaystyle \delta } consists of the following six instructions:

In words, the first two instructions say that in state p any time the symbol 0 is read, one A is pushed onto the stack. Pushing symbol A on top of another A is formalized as replacing top A by AA (and similarly for pushing symbol A on top of a Z).

The third and fourth instructions say that, at any moment the automaton may move from state p to state q.

The fifth instruction says that in state q, for each symbol 1 read, one A is popped.

Finally, the sixth instruction says that the machine may move from state q to accepting state r only when the stack consists of a single Z.

There seems to be no generally used representation for PDA. Here we have depicted the instruction (p, a, A, q, α) {\displaystyle (p,a,A,q,\alpha)} by an edge from state p to state q labelled by a; A / α {\displaystyle a;A/\alpha } (read a; replace A by α {\displaystyle \alpha }).