Pushdown Automaton

computation

Definition

Pushdown Automaton Criterion

A Turing machine satisfies the pushdown automaton criterion if

1. on the input tape it can never move to the left, and
2. for the read/write head on the work tape, in every configuration it holds that:

• to the left of the head there can only be non-blank symbols, and
• to the right of the head there can only be blank symbols

The machines behaves like a stack.

Normal Form

A pushdown automaton can accept in two standard ways:

1. by entering an accepting state after reading the whole input word, or
2. by emptying the stack.

A useful normal form combines both acceptance conditions.

Normal Form of a Pushdown Automaton

A pushdown automaton is in normal form if it accepts an input word exactly when, in one transition, it

1. reads the right boundary symbol $Z_2$ of the input,
2. reads the bottom stack symbol, and
3. enters its unique accepting state.

Thus, the automaton accepts simultaneously by final state and by empty stack.

In this form, acceptance is only possible after the complete input has been read and the stack has been reduced to its bottom symbol.

Intuition

The automaton may accept only in the moment when the input head reaches $Z_2$ and the stack has been reduced to its bottom symbol $Z_0$. The transition then moves into the unique accepting state.

Examples

A pushdown automaton in normal form for $\{0^n{1}^{2n+1}\mid n\ge 0\}$

The following pushdown automaton in normal form accepts

$$L=\{0^n{1}^{2n+1}\mid n\ge 0\}$$

with

$$M=(\{q_0,q_1,q_2,q_f\},\{0,1\},\{Z_0,A\},\delta ,q_0,\{Z_0,Z_1,Z_2\},\{q_f\})$$

where:

$$\begin{array}{rl}\delta (q_0,0,B)& =\{(q_1,A,S,R)\}\\ \delta (q_1,0,B)& =\{(q_0,A,R,R)\}\\ \delta (q_0,1,B)& =\{(q_2,B,R,L)\}\\ \delta (q_2,1,A)& =\{(q_2,B,R,L)\}\\ \delta (q_2,Z_2,Z_0)& =\{(q_f,Z_0,S,R)\}\end{array}$$

The first two transitions push one $A$ for every two $0$ symbols. After that, the automaton reads one initial $1$, then removes one $A$ for each further $1$. It accepts when the input head reaches $Z_2$ and the stack has been reduced to $Z_0$.