This page lists some examples of pushdown automata and their accepted languages as well as the possibility to generate an equivalent grammar for these automata. In most cases, we also list some equivalent context-free grammars.

{ a^n b^n | n>0 }

The idea of the following PDA is to shift the prefix of a's to the stack so that the stack consists of $a...a. Once the first occurrence of b is read, we switch to state q0 where we match the expected b's with the a's on the stack.

PDA	states: q0,q1 sigmaPD: $,a,b sigmaIN: a,b transitions: ($,q0,a,$a,q0); (a,q0,a,aa,q0); (a,q0,b,ϵ,q1); ($,q1,ϵ,ϵ,q1); (a,q1,b,ϵ,q1);

equivalent grammars are

S -> aB
B -> b | aBb

and

S -> aSb | ab

{ a^n b^n | n≥0 }

The idea of the following PDA is the same as in the previous example. The PDA just has an additional transition ($,q0,ϵ,ϵ,q0) which allows the automaton in the initial state to empty the stack.

PDA	states: q0,q1 sigmaPD: $,a,b sigmaIN: a,b transitions: ($,q0,ϵ,ϵ,q0); ($,q0,a,$a,q0); (a,q0,a,aa,q0); (a,q0,b,ϵ,q1); ($,q1,ϵ,ϵ,q1); (a,q1,b,ϵ,q1);

equivalent grammars are

S -> aB | ϵ
B -> b | aBb

and

S -> aSb | ϵ

{ a^m b^n | n≥m≥0 }

We first shift in q0 the prefix of a's to the stack so that the stack content is $a...a. Once the first b is read, we switch to q1 where we match the b's with the a's. In q1 the stack must become empty before the word is completely read since we can only to state q2 with stack content $. In state q2, we consume the remaining b's from the input word.

PDA	states: q0,q1,q2 sigmaPD: $,a,b sigmaIN: a,b transitions: ($,q0,ϵ,ϵ,q2); ($,q0,a,$a,q0); ($,q0,b,$,q2); (a,q0,a,aa,q0); (a,q0,b,ϵ,q1); (a,q1,b,ϵ,q1); ($,q1,ϵ,ϵ,q2); ($,q1,b,$,q2); ($,q2,b,$,q2); ($,q2,ϵ,ϵ,q2);

equivalent grammars are

S -> bC | aBC | ϵ
C -> bC | ϵ
B -> b | aBb

and

S -> B | aAB
A -> b | aAb
B -> bB | ϵ

{ a^n b^m | n≥m≥0 }

We first shift in q0 the prefix of a's to the stack so that the stack content is $a...a. Once the first b is read, we switch to q1 where we match the b's with the a's. If the input word has been read, we switch to state q2 where we consume the remaining a's from the stack.

PDA	states: q0,q1,q2 sigmaPD: $,a,b sigmaIN: a,b transitions: ($,q0,ϵ,ϵ,q2); ($,q0,a,$a,q0); (a,q0,a,aa,q0); (a,q0,b,ϵ,q1); (a,q1,b,ϵ,q1); (a,q1,ϵ,ϵ,q2); ($,q1,ϵ,ϵ,q2); (a,q2,ϵ,ϵ,q2); ($,q2,ϵ,ϵ,q2);

equivalent grammars are

S -> aB | aC | ϵ
C -> aB | aC
B -> b | aBb

and

S -> ϵ | aS | aA
A -> b | aAb

{ a^{2n+1) b^n | n≥0 }

We first shift in q0 the prefix of a's to the stack so that the stack content is $a...a. Once the first b is read, we switch to q1 where we match each b's with two a's on the stack. To this end, we switch to state q1 when b is read removing one a from the stack, and in q1, we do not read an input symbol, but remove another a from the stack before switching back to q1.

PDA	states: q0,q1,q2,q3 sigmaPD: $,a sigmaIN: a,b transitions: ($,q0,a,$a,q0); (a,q0,a,aa,q0); (a,q0,b,ϵ,q1); (a,q0,ϵ,ϵ,q3); (a,q1,ϵ,ϵ,q2); (a,q2,b,ϵ,q1); (a,q2,ϵ,ϵ,q3); ($,q3,ϵ,ϵ,q3);

equivalent grammars are

S -> aZ
Z -> ϵ | aaB
B -> b | aaBb

and

S -> aA
A -> aaSb | ϵ

{ w | #(a,w) = #(b,w) > 0 }

The automaton has three states q0,qa,qb. When reading the word from left to right, we match a's with b's and remember on the stack the additional occurrences of a's and b's that were not yet matched. Hence, if more a's than b's occurred so far, we are in state qa where the stack content is $a...a and if more b's than a's occurred so far, we are in state qb where the stack content is $b...b. When the entire word has been read, we must have a stack content $ (but note that this may happen in between also), and we then also remove $ from the stack.

PDA	states: q0,qa,qb sigmaPD: $,a,b sigmaIN: a,b transitions: ($,q0,a,$a,qa); ($,q0,b,$b,qb); (a,qa,a,aa,qa); (a,qa,b, ϵ,qa); ($,qa,a,$a,qa); ($,qa,b,$b,qb); ($,qa,ϵ,ϵ ,qb); (b,qb,a,ϵ,qb); (b,qb,b,bb,qb); ($,qb,a,$a,qa); ($,qb,b,$b,qb); ($,qb,ϵ,ϵ,qb);

equivalent grammar

S -> bAC | aBC
C -> ϵ | bAC | aBC
A -> a | bAA
B -> b | aBB

and also

S -> aSbS | bSaS

{ w | #(a,w) = #(b,w) ≥ 0 }

The idea is the same as in the example before, there is just another transition to accept the empty word.

PDA	states: q0,qa,qb sigmaPD: $,a,b sigmaIN: a,b transitions: ($,q0,ϵ,ϵ,q0); ($,q0,a,$a,qa); ($,q0,b,$b,qb); (a,qa,a,aa,qa); (a,qa,b, ϵ,qa); ($,qa,a,$a,qa); ($,qa,b,$b,qb); ($,qa,ϵ,ϵ ,qb); (b,qb,a,ϵ,qb); (b,qb,b,bb,qb); ($,qb,a,$a,qa); ($,qb,b,$b,qb); ($,qb,ϵ,ϵ,qb);

equivalent grammar

S -> ϵ | bAS | aBS
A -> a | bAA 
B -> b | aBB

and also

S -> ϵ | aSbS | bSaS

and also

S -> ϵ | SS | aSb | bSa

{ w | #(a,w) ≠ #(b,w) }

The idea is the same as in the previous two examples but instead of accepting the word by emptying the stack when the word has been read, we switch to state qf provided that there is another a or b on the stack, and in state qf, we then empty the stack.

PDA	states: q0,qa,qb,qf sigmaPD: $,a,b sigmaIN: a,b transitions: ($,q0,a,$a,qa); ($,q0,b,$b,qb); (a,qa,a,aa,qa); (a,qa,b, ϵ,qa); (a,qa,ϵ, ϵ,qf); ($,qa,a,$a,qa); ($,qa,b,$b,qb); (b,qb,a,ϵ,qb); (b,qb,b,bb,qb); (b,qb,ϵ, ϵ,qf); ($,qb,a,$a,qa); ($,qb,b,$b,qb); (a,qf,ϵ,ϵ,qf); (b,qf,ϵ,ϵ,qf); ($,qf,ϵ,ϵ,qf);

equivalent grammar

S -> aBS | bAS | aC | bD
A -> a | bAA
B -> b | aBB
C -> ϵ | aBC | aC
D -> ϵ | bAD | bD

{ w | #(a,w) < #(b,w) }

The idea is the same as in the previous example but this automaton is not symmetric in that switching to qf is not allowed by transition (a,qa,ϵ, ϵ,qf) anymore and only by (b,qb,ϵ, ϵ,qf) to make sure that there were more b's.

PDA	states: q0,qa,qb,qf sigmaPD: $,a,b sigmaIN: a,b transitions: ($,q0,a,$a,qa); ($,q0,b,$b,qb); (a,qa,a,aa,qa); (a,qa,b, ϵ,qa); ($,qa,a,$a,qa); ($,qa,b,$b,qb); (b,qb,a,ϵ,qb); (b,qb,b,bb,qb); (b,qb,ϵ, ϵ,qf); ($,qb,a,$a,qa); ($,qb,b,$b,qb); (b,qf,ϵ,ϵ,qf); ($,qf,ϵ,ϵ,qf);

equivalent grammar

S -> aBS | bAS | bD
A -> a | bAA
B -> b | aBB
D -> ϵ | bAD | bD

{ a^m b^n c^{m+n} | m,n≥0 }

This example shows that we can enumerate all addition equations of two unary number, i.e., numbers where number n is encoded by n symbols aⁿ, bⁿ, or cⁿ. The idea of the PDA is to shift first the a's on the stack in state qa, then the b's in state qb, and then in state qc only c's are allowed to be read which are matched with symbols on the stack. If the input word is empty, the stack content must be $ which is then removed also.

PDA	states: q0,qa,qb,qc sigmaPD: $,a,b sigmaIN: a,b,c transitions: ($,q0,ϵ,ϵ,qc); ($,q0,a,$a,qa); ($,q0,b,$b,qb); (a,qa,a,aa,qa); (a,qa,b,ab,qb); (a,qa,c,ϵ,qc); (b,qb,b,bb,qb); (b,qb,c,ϵ,qc); (a,qc,c,ϵ,qc); (b,qc,c,ϵ,qc); ($,qc,ϵ,ϵ,qc);

equivalent grammar

S -> ϵ | aB | bC
B -> c | bCc | aBc
C -> c | bCc

and also

S -> B | aSc
B -> bBc | ϵ

{ a^{m+n} b^m c^n | m,n>=0 }

This example is similar to the previous one: In state qa, we first shift all a's on the stack, and match them in state qb with a sequence of b's, and after that in state qc with a sequence of c's. If the word has been read, we expect the stack content $ which is then removed also.

PDA	states: q0,qa,qb,qc sigmaPD: $,a,b sigmaIN: a,b,c transitions: ($,q0,ϵ,ϵ,qc); ($,q0,a,$a,qa); (a,qa,a,aa,qa); (a,qa,b,ϵ,qb); (a,qa,c,ϵ,qc); (a,qb,b,ϵ,qb); (a,qb,c,ϵ,qc); (a,qc,c,ϵ,qc); ($,qc,ϵ,ϵ,qc);

equivalent grammar

S -> aA | ϵ
A -> c | aBc | aAc
B -> b | aBb

and also

S -> B | aSc
B -> aBb | ϵ

All words wcw' where w' is the mirror of w and wϵ{a,b}^*

This is a classic example: In state q0, we shift all symbols read from the input word onto the stack until we read c. Once that happens, we switch to state q1 where input symbols read from the input word must be matched with the topmost symbol on the stack. If the word has been read, we expect the stack content $ which is then removed also. Note that without a symbol c in the middle, we would not know when to switch to state q1 which would make the automaton nondeterministic. Having the middle symbol c, we even obtain LL(1) grammars for deterministic parsing.

PDA	states: q0,q1 sigmaPD: $,a,b sigmaIN: a,b,c transitions: ($,q0,c,ϵ,q1); ($,q0,a,$a,q0); ($,q0,b,$b,q0); (a,q0,a,aa,q0); (a,q0,b,ab,q0); (a,q0,c,a,q1); (b,q0,a,ba,q0); (b,q0,b,bb,q0); (b,q0,c,b,q1); (a,q1,a,ϵ,q1); (b,q1,b,ϵ,q1); ($,q1,ϵ,ϵ,q1);

equivalent grammar

S -> aA | bB | c
B -> cb | bBb | aAb
A -> ca | aAa | bBa

and also

S -> aSa | bSb | c

All words ww' where w' is the mirror of w and wϵ{a,b}^*

This is a modification of the previous example where we remove the middle symbol c. There is no longer a deterministic PDA for this example, and therefore deterministic parsing is not possible. Hence, there is also no LR(1) grammar for this example, and therefore, there is also no LL(1) grammar for it.

PDA	states: q0,q1 sigmaPD: $,a,b sigmaIN: a,b transitions: ($,q0,ϵ,ϵ,q1); ($,q0,a,$a,q0); ($,q0,b,$b,q0); (a,q0,a,aa,q0); (a,q0,b,ab,q0); (a,q0,ϵ,a,q1); (b,q0,a,ba,q0); (b,q0,b,bb,q0); (b,q0,ϵ,b,q1); (a,q1,a,ϵ,q1); (b,q1,b,ϵ,q1); ($,q1,ϵ,ϵ,q1);

equivalent grammar

S -> aA | bB | ϵ
A -> a | aAa | bBa
B -> b | bBb | aAb

and also

S -> aSa | bSb | ϵ

Balanced Parentheses

In this example, you may read 'a' as '(' and 'b' as ')'. The words must be those where each 'a' is matched with a 'b' such that in between all matched expressions could be removed. The idea of the PDA is very simple: We only have one state where we push every a read from the input word onto the stack. Whenever a 'b' is read, we match it with the topmost 'a' on the stack, and finally the stack must be $.

PDA	states: q0 sigmaPD: $,a,b sigmaIN: a transitions: ($,q0,ϵ,ϵ,q0); ($,q0,a,$a,q0); (a,q0,a,aa,q0); (a,q0,b,ϵ,q0);

equivalent grammar

S -> aBS | ϵ
B -> b | aBB

and also

S -> aSbS | ϵ