Pushdown Automata

Text Book: Peter Linz

Prepared by : Dr. Ravi B

November 26, 2022

1 Introduction
Pushdown Automata (pda) is a class of automata tgat can be associated with context-free gram-
mars. Thus pda is an automaton that accepts exactly the family of context-free languages. There
are two types of pda
1.Non-deterministic pda (npda)
2.Deterministic pda (dpda)
dpda has a limitation on the set of context-free languages that it can accept, while npda ccepts
exactly the family of context-free languages.In otherwords, any context-free language can be repre-
sented by an npda.

2 Schematic Representation
chematic representation of a pushdown automaton is given in Figure. pda uses an unbounded stack
as its storage. Each move of the control unit reads a symbol from the input file, while at the same
time changing the contents of the stack through the usual stack operations. Each move of the control
unit is determined by the current input symbol as well as by the symbol currently on top of the
stack. The result of the move is a new state of the control unit and a change in the top of the stack.

1
 Figure 1: Schematic representation of pda

3 Nondeterministic Pushdown Automata(npda)

A nondeterministic pushdown accepter (npda) is defined by the septuple
M = (Q, Σ, τ, δ, q0 , z, F )
where
Q is a finite set of internal states of the control unit
Σ is the input alphabet
τ is a finite set of symbols called the stack alphabet
δ : Q × (Σ ∪ λ) × τ → Q × τ ∗ is the transition function
q0 ∈ Q is the initial state of the control unit
z ∈ τ is the stack start symbol
F ⊆ Q is the set of final states.
The arguments of δ are the current state of the control unit, the current input symbol, and the
current symbol on top of the stack. The result is a set of pairs (q, x), where q is the next state of
the control unit and x is a string that is put on top of the stack in place of the single symbol there
before. Note that the second argument of δ may be λ, indicating that a move that does not consume
an input symbol is possible. We will call such a move a λ-transition. Note also that δ is defined

2
so that it needs a stack symbol; no move is possible if the stack is empty. Finally, the requirement
that the elements of the range of δ be a finite subset is necessary because Q × τ ∗ is an infinite set
and therefore has infinite subsets. While an npda may have several choices for its moves, this choice
must be restricted to a finite set of possibilities.
Suppose the set of transition rules of an npda contains
δ(q1 , a, b) = {(q2 , cd), (q3 , λ)}
If at any time the control unit is in state q1 , the input symbol read is a, and the symbol on top of
the stack is b, then one of two things can happen:
(1) the control unit goes into state q2 and the string cd replaces b on top of the stack,
or (2) the control unit goes into state q3 with the symbol b removed from the top of the stack.
In our notation we assume that the insertion of a string into a stack is done symbol by symbol,
starting at the right end of the string.

3.1 Instantaneous Description (ID)

The triplet,
(q, w, u)
where q is the state of the control unit, w is the unread part of the input string, and u is the
stack contents (with the leftmost symbol indicating the top of the stack), is called an instantaneous
description of a pushdown automaton. A move from one instantaneous description to another will
be denoted by ⊢ the symbol; thus
(q1 , aw, bx) ⊢ (q2 , w, yx)
is possible if and only if
(q2 , y) ∈ (q1 , a, b)
Moves involving an arbitrary number of steps will be denoted by ⊢∗ . The expression
(q1 , w1 , x1 ) ⊢ (q2 , w2 , x2 )
indicates a possible configuration change over a number of steps.

4 The Language Accepted by a Pushdown Automaton

Let M = (Q, Σ, τ, δ, q0 , z, F ) be pda. The language accepted by M is defined as
L(M ) = {w ∈ Σ∗ : (q0 , w, z) ⊢∗ (p, λ, u), p ∈ F, u ∈ τ ∗ }

3
In words, the language accepted by M is the set of all strings that can put M into a final state at
the end of the string. The final stack content u is irrelevant to this definition of acceptance.

5 Transition diagram for npda

We can also use transition graphs to represent npda’s. In this representation we label the edges of
the graph with three things: the current input symbol, the symbol at the top of the stack, and the
string that replaces the top of the stack.
Example:
Consider the followig npda with,
Q = {q0 , q1 , q2 , q3 }
Σ = {a, b}
τ = {0, 1}
z=0
F = {q3 }
q0 = q0
and the following transitions
δ(q0 , a, 0) = {(q1 , 10), (q3 , λ)}
δ(q0 , λ, 0) = (q3 , λ)
δ(q1 , a, 1) = (q1 , 11)
δ(q1 , b, 1) = (q2 , λ)
δ(q2 , b, 1) = (q2 , λ)
δ(q2 , λ, 0) = (q3 , λ)
The transition diagram for the above npda is given below

4
 Figure 2: Transition Diagram

6 Problems
1. Design an npda for L = {an bn : n ≥ 1}. Show the IDs for w = aabb
The solution is to push all a’s onto the stack and then do the pop operation for each input
b. If the stack is empty when the end of the string is reached then the input string is in L.
Othewrise the string is not in L.
Thus, we design npda with,
Q = {q0 , q1 , qf }
Σ = {a, b}
τ = {a, b}
z=z
F = {qf }
q0 = q0
and with transitions :
δ(q0 , a, z) = (q0 , az)
δ(q0 , a, a) = (q0 , aa)
δ(q0 , b, a) = (q1 , λ)
δ(q1 , b, a) = (q1 , λ)
δ(q1 , λ, z) = (qf , λ)
IDs
(q0 , aabb, z) ⊢ (q0 , abb, az) ⊢ (q0 , bb, aaz) ⊢ (q1 , b, az) ⊢ (q1 , λ, z) ⊢ (qf , λ, λ)

5
2. Design an npda for L = {an b2n : n ≥ 1}. Show the moves made by the npda for w = aabbbb
The solution is to push 2 a’s onto the stack for each input a and then do the pop operation
for each input b. If the stack is empty when the end of the string is reached then the input
string is in L. Othewrise the string is not in L.
Thus, we design npda with,
Q = {q0 , q1 , qf }
Σ = {a, b}
τ = {a, b}
z=z
F = {qf }
q0 = q0
and with transitions :
δ(q0 , a, z) =0 , aaz)
δ(q0 , a, a) =0 , aaa)
hspace*1cm δ(q0 , b, a) =1 , λ)
δ(q1 , b, a) =1 , λ)
δ(q1 , λ, z) = {(qf , λ)
IDs
(q0 , aabbbb, z) ⊢ (q0 , abbbb, aaz) ⊢ (q0 , bbbb, aaaaz) ⊢ (q1 , bbb, aaaz) ⊢ (q1 , bb, aaz) ⊢ (q1 , b, az) ⊢
(q1 , λ, z) ⊢ (qf , λ, λ)

3. Design an npda for L = {an bm : n < m, n ≥ 0}.

The idea is to push all a’s onto the stack and then do the pop operation for each input b. If
the stack is empty before we reach the end of the input string then the input string is in L.
We then simply advance the pointer to the end of the string. Othewrise the string is not in L.
Thus, we design npda with,
Q = {q0 , q1 , q2 , qf }
Σ = {a, b}
τ = {a, b}
z=z
F = {qf }
q0 = q0
and with transitions :

6
 δ(q0 , a, z) = (q0 , az)
δ(q0 , b, z) = (q2 , z) (only b’s)
δ(q0 , a, a) = (q0 , aa)
δ(q0 , b, a) = (q1 , λ)
δ(q1 , b, a) = (q1 , λ)
δ(q1 , b, z) = (q2 , z)
δ(q2 , b, z) = (q2 , z)
δ(q2 , λ, z) = (qf , λ)

4. Design an npda for L = {an bm : n > m, m ≥ 0}.

The idea is to push all a’s onto the stack and then pop for each b. If we reach the end of the
input string and the stack has atleat one a then the input string is in L. Othewrise the string
is not in L.
Thus, we design npda with,
Q = {q0 , q1 , qf }
Σ = {a, b}
τ = {a, b}
z=z
F = {qf }
q0 = q0
and with transitions :
δ(q0 , a, z) = (q0 , az)
δ(q0 , a, a) = (q0 , aa)
δ(q0 , λ, a) = (qf , λ) (only a’s)
δ(q0 , b, a) = (q1 , λ)
δ(q1 , b, a) = (q1 , λ)
δ(q1 , λ, a) = {(qf , λ)

5. Design an npda for L = {an bm : n ̸= m, n ≥ 0, m ≥ 0}. (Exercise)

6. Find an npda for L = {wcwR : w ∈ {a, b}∗ }.

We push all symbols before c onto the stack. When c is encountered we simply advance the
pointer and change the state. After c, if each input symbol matches with the top of the stack
then we do the pop operation. If we reach the end of the input string and the stack is empty,

7
 then the input string is in L. Othewrise the string is not in L.
Thus, we design npda with,
Q = {q0 , q1 , qf }
Σ = {a, b}
τ = {a, b}
z=z
F = {qf }
q0 = q0
and with transitions :
δ(q0 , a, z) = (q0 , az)
δ(q0 , b, z) = (q0 , bz)
δ(q0 , a, a) = (q0 , aa)
δ(q0 , a, b) = (q0 , ab)
δ(q0 , b, b) = (q0 , bb)
δ(q0 , b, a) = (q0 , ba)
δ(q0 , c, a) = (q1 , a)
δ(q0 , c, b) = (q1 , b)
δ(q1 , a, a) = (q1 , λ)
δ(q1 , b, b) = (q1 , λ)
δ(q1 , λ, z) = (qf , λ)

7. Find an npda for L = {wwR : w ∈ {a, b}∗ }.

We use the same method as in the above problem. However, an apparent difficulty with this
problem is that we do not know the middle of the string, that is, where w ends and wR
starts. But the nondeterministic nature of the automaton helps us with this; the npda cor-
rectly guesses where the middle is and switches states at that point.
To correctly guesses where the middle is and to change the state at that point, we use the
followig two transitions
δ(q0 , λ, a) = (q1 , a)
δ(q0 , λ, b) = (q1 , b)
Thus, we design npda with,
Q = {q0 , q1 , qf }
Σ = {a, b}

8
 τ = {a, b}
z=z
F = {qf }
q0 = q0
and with transitions :
δ(q0 , a, z) = (q0 , az)
δ(q0 , b, z) = (q0 , bz)
δ(q0 , a, a) = (q0 , aa)
δ(q0 , a, b) = (q0 , ab)
δ(q0 , b, b) = (q0 , bb)
δ(q0 , b, a) = (q0 , ba)
δ(q0 , λ, a) = (q1 , a)
δ(q0 , λ, b) = (q1 , b)
δ(q1 , a, a) = (q1 , λ)
δ(q1 , b, b) = (q1 , λ)
δ(q1 , λ, z) = (qf , λ)
Let w = abbbba then thge moves made by the npda are
(q0 , abbbba, z) ⊢ (q0 , bbbba, az) ⊢ (q0 , bbba, baz) ⊢ (q0 , bba, bbaz) ⊢ (q1 , bba, bbaz) ⊢ (q1 , ba, baz) ⊢
(q1 , a, az) ⊢ (q1 , λ, z) ⊢ (qf , λ, λ)

8. Find an npda for L = {an bm cn+m : n ≥ 0, m ≥ 0}.

Push all a’s and b’s onto the stack and then pop for each c. If we reach the end of the input
string and the stack is empty, then the input string is in L. Othewrise the string is not in L.
The followig cases must be considered
When n = 0, and m = 0, then w = λ
When n = 0, and m > 0, then w = bm cm
When n > 0, and m = 0, then w = an cn
When n > 0, and m > 0, then w = an bm cn+m
Thus, we design npda with,
Q = {q0 , q1 , q2 , qf }
Σ = {a, b}
τ = {a, b}
z=z

9
 F = {qf }
q0 = q0
and with transitions :
δ(q0 , λ, z) = (qf , λ) (λ is accepted)
δ(q0 , a, z) = (q0 , az)
δ(q0 , b, z) = (q1 , bz) ( to accept bm cm )
δ(q0 , a, a) = (q0 , aa)
δ(q0 , c, a) = (q2 , λ) (to accept an cn )
δ(q0 , b, a) = (q1 , ba) (to accept an bm cn+m )
δ(q1 , b, b) = (q1 , bb)
δ(q1 , c, b) = (q2 , λ)
δ(q2 , c, a) = (q2 , λ)
δ(q2 , c, b) = (q2 , λ)
δ(q2 , λ, z) = (qf , λ)

9. Find an npda for L = {w : na (w) = nb (w), w ∈ {a, b}∗ }.

The solution for this problem is shown in the followig table

Table 1: Method

Input Symbol Stack Top Action

a z Push a
b z Push b
a a Push a
a b Pop
b b Push b
b a Pop

Followig the above method, we find that when reach the end of the input string the stack must
be empty if the string is in L.
Thus, we design npda with,
Q = {q0 , qf }
Σ = {a, b}
τ = {a, b}

10
 z=z
F = {qf }
q0 = q0
and with transitions :
δ(q0 , a, z) = (q0 , az)
δ(q0 , b, z) = (q0 , bz)
δ(q0 , a, a) = (q0 , aa)
δ(q0 , b, b) = (q0 , bb)
δ(q0 , a, b) = (q0 , λ)
δ(q0 , b, a) = (q0 , λ)
δ(q0 , λ, z) = (qf , λ)

10. Construct an npda for L = {an bm : 2n ≤ m ≤ 3n}.

When n = 0, and m = 0,
When n = 1, and m = 2, 3
When n = 2, and m = 4, 5, 6
When n = 3, and m = 6, 7, 8, 9
and so on
Thus, the idea is to push 2 a’s for each and then do pop operation for each b. When reach the
end of the string the stack must be empty of the string is in L. Otherwise the string dees not
belong to L
Thus, we design npda with,
Q = {q0 , q1 , qf }
Σ = {a, b}
τ = {a, b}
z=z
F = {qf }
q0 = q0
and with transitions :
δ(q0 , λ, z) = (qf , λ)
δ(q0 , a, z) = (q0 , aaz)
δ(q0 , a, a) = (q0 , aaa)

11
 δ(q0 , b, a) = (q1 , λ)
δ(q1 , b, a) = (q1 , λ)
δ(q1 , λ, z) = (qf , λ)

11. Design an npda for L = {an bm : 0 ≤ n ≤ m ≤ 3n}. (Exercise)

12. Design an npda for L = {an bn+m cm : n ≥ 0, m ≥ 0}. (Exercise)

13. Design an npda for L = {a3 bn cn : n ≥ 0}. (Exercise)

14. Design an npda for L = {w : na (w) = nb (w) + 1, w ∈ {a, b}∗ }. (Exercise)

15. Design an npda for L = {w : na (w) < nb (w), w ∈ {a, b}∗ }. (Exercise)

16. Find an npda on Σ = {a, b, c} that accepts the language

L = {w1 cw2 : w1 , w2 ∈ {a, b}∗ , w1 ̸= w2R } (Exercise)

17. Find an npda L = {ab(ab)n b(ba)n : n ≥ 0} (Exercise)

12