Editing Pushdown automaton (section)

== Example ==

The following is the formal description of the PDA which recognizes the language <math>\{0^n1^n \mid n \ge 0 \}</math> by final state:

[[Image:Pda-example.svg|thumb|200px|PDA for <math>\{0^n1^n \mid n \ge 0\}</math><br/>(by final state)]]
<math>M=(Q,\  \Sigma,\  \Gamma,\  \delta, \ q_{0},\ Z, \ F)</math>, where

*'''states:''' <math>Q = \{ p,q,r \}</math>
*'''input alphabet:''' <math>\Sigma = \{0, 1\}</math>
*'''stack alphabet:''' <math>\Gamma = \{A, Z\}</math>
*'''start state:''' <math>q_{0} = p</math>
*'''start stack symbol:''' {{mvar|Z}}
*'''accepting states:''' <math>F = \{r\}</math>

The transition relation <math>\delta</math> consists of the following six instructions:

:<math>(p,0,Z,p,AZ)</math>,
:<math>(p,0,A,p,AA)</math>,
:<math>(p,\epsilon,Z,q,Z)</math>,
:<math>(p,\epsilon,A,q,A)</math>,
:<math>(q,1,A,q,\epsilon)</math>, and
:<math>(q,\epsilon,Z,r,Z)</math>.

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

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

The fifth instruction says that in state {{mvar|q}}, for each symbol {{val|1}} read, one {{mvar|A}} is popped.

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

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

=== Explanation ===
[[Image:Pda-steps.svg|thumb|214px|accepting computation for {{val|0011}}]]
The following illustrates how the above PDA computes on different input strings. The subscript {{mvar|M}} from the step symbol <math>\vdash</math> is here omitted.
{{ordered list|type=lower-alpha
|1= Input string = 0011. There are various computations, depending on the moment the move from state {{mvar|p}} to state {{mvar|q}} is made. Only one of these is accepting.
{{ordered list|type=lower-roman
| <math>(p,0011,Z) \vdash (q,0011,Z) \vdash (r,0011,Z)</math><br/>The final state is accepting, but the input is not accepted this way as it has not been read.
| <math>(p,0011,Z) \vdash (p,011,AZ) \vdash (q,011,AZ)</math><br/>No further steps possible.
| <math>(p,0011,Z) \vdash (p,011,AZ) \vdash (p,11,AAZ) \vdash (q,11,AAZ) \vdash (q,1,AZ) \vdash (q,\epsilon,Z) \vdash (r,\epsilon,Z)</math><br/>Accepting computation: ends in accepting state, while complete input has been read.}}
|2= Input string = 00111. Again there are various computations. None of these is accepting.
{{ordered list|type=lower-roman
| <math>(p,00111,Z) \vdash (q,00111,Z) \vdash (r,00111,Z)</math><br/>The final state is accepting, but the input is not accepted this way as it has not been read.
| <math>(p,00111,Z) \vdash (p,0111,AZ) \vdash (q,0111,AZ)</math><br/>No further steps possible.
| <math>(p,00111,Z) \vdash (p,0111,AZ) \vdash (p,111,AAZ) \vdash (q,111,AAZ) \vdash (q,11,AZ) \vdash (q,1,Z) \vdash (r,1,Z)</math><br/>The final state is accepting, but the input is not accepted this way as it has not been (completely) read.}}
}}