Pushdown Automata-PDA
Prof. (Dr.) K.R. Chowdhary
Email: kr.chowdhary@iitj.ac.in
Formerly, Prof. & Head, Department of CS
MBM Engineering College, Jodhpur

Saturday 19th July, 2025

kr chowdhary

TOC

1/ 8

K.R. Chowdhary

Theory of Computation
Automata, Formal Languages, Computation and Complexity
Focuses on pedagogy in its writing, that represents a refreshing
approach
Ensures comprehensive and enjoyable learning
Undergone a rigorous classroom testing

©2025

Get 20% off with this code: SPRAUT
Available on Springer Nature Link
Please note that promotional coupons are only valid for English-language Springer, Apress, and Palgrave Macmillan books
& eBooks and are redeemable on link.springer.com only. Titles affected by fixed book price laws, forthcoming titles and
titles temporarily not available on Springer Nature Link are excluded from promotions, as are reference works, handbooks,
encyclopedias, subscriptions, or bulk purchases. The currency in which your order will be invoiced depends on the billing
address associated with the payment method used, not necessarily your home currency. Regional VAT/tax may apply.
Promotional prices may change due to exchange rates. Promotions are valid for individual customers only. Booksellers,
book distributors, and institutions such as libraries and corporations please visit springernature.com/contact-us.
Promotions do not work in combination with other discounts or gift cards.

link.springer.com/book/
9789819762347

Introduction to Pushdown Automata (PDA)

Definition
A PDA consists: a infinite tape, a read head, set of states, and a start
state. The additional components from FA are: Pushdown stack, initial
symbol on stack, and stack alphabets (Γ). PDA M = (Q, Σ, δ , s, Γ, Z0 , F ),
where,
Q is finite set of states,
Σ is finite set of terminal symbols (language alphabets),
s start state (q0 ), F is final state.
δ is transition function: δ : Q × (Σ ∪ {ε}) × Γ → finite subset of
Q × Γ.

The transition function of a PDA is so defined, because a PDA may have
transitions without any input read.

kr chowdhary

TOC

2/ 8

Introduction to PDA
The PDA has two types of storage; 1) infinite tape, just like the FA, 2)
pushdown stack, is read-write memory of arbitrary size, with the
restriction that it can be read or written at one end only.
Input tape
a

a

b

a

a

Read head

b

b
Direction of head move

Finite
Control

a

stack top

b
Stack
a
Z0 stack bottom

Definition
ID (Instantaneous Description) of a PDA is: ID : Q × Σ∗ × Γ∗ , start-id
∈ {q0 } × Σ∗ × {Z0 }, e.g., start ID may be (q0 , aaa, Z0 ).
kr chowdhary

TOC

3/ 8

PDA Transitions
δ (q, a, Z ) = finite subset of {(p1 , β1 ), (p2 , β2 ), . . . , (pm , βm )}. Therefore,
(pi , βi ) ∈ δ (q, a, z)), for 1 ≤ i ≤ m.
By default, a PDA is non-derministic machine. Due to this fact, a PDA
can manipulate the stack without any input from tape. Following are
some of the transitions in PDA:
Case - (a): A PDA currently
in state q, stack symbol A,
with input ε, moves to state q
and write ε on the stack:
δ (q, ε, A) = (q, ε).
Case - (b): A PDA currently
in state q, with ε input, and
stack symbol ε, moves to
state q, and writes A on stack:
δ (q, ε, ε) = (q, A).
Case - (c): A PDA in state q,

kr chowdhary

reads input a, with stack
symbol Z , moves to state p
and write β on stack:
δ (q, a, Z ) = (p, β ).
ε, A/ε

ε, ε/A

q

q

(q, ε) ∈ δ(q, ε, A)

(q, A) ∈ δ(q, ε, ε)

(a)

(b)

TOC

q

a, Z/β

p

(p, β) ∈ δ(q, a, Z)
(c)

4/ 8

Language recognition: an b n
A move of a PDA is defined as (q, ax, Z α) ⊢M (q ′ , x, β α), if
(q ′ , β ) ∈ (q, a, Z ). (In Z α, Z is top symbol on stack)
Example
Construct a PDA to recognize L = {an b n |n ≥ 0}.
M = (Q, Σ, δ , s, F , Γ, Z0 ),
Σ = {a, b}, Γ = {A}
Q = {q0 , q1 , q2 , q3 }, F = {q0 , q3 }
δ (q0 , ε, ε) = (q1 , Z0 )
δ (q1 , a, ε) = (q1 , A)
δ (q1 , b, A) = (q2 , ε)
δ (q2 , b, A) = (q2 , ε)
δ (q2 , ε, Z0 ) = (q3 , ε)

⊢ (q2 , b, AZ0 ),

⊢ (q2 , ε, Z0 ),

⊢ (q3 , ε, ε), the PDA halts & accepts.
a, ε/A

q0

ε, ε/Z0

q1
b, A/ε

(q0 , aabb, ε) ⊢ (q1 , aabb, Z0 )

q3

⊢ (q1 , abb, AZ0 )

⊢ (q1 , bb, AAZ0 )
kr chowdhary

ε, Z0 /ε

q2

b, A/ε
TOC

5/ 8

Language Recognition: wcw R
Example
Construct a PDA to recognize L = {wcw R |w ∈ {a, b}∗ }.
Solution: Transition function,
moves, and PDA:

d, ε/d

M = (Q, Σ, δ , s, F , Γ, Z0 )

q0

Σ = {a, b, c}, d ∈ {a, b},

Q = {q0 , q1 , q2 }, F = {q2 },
Γ = {a, b, Z0 }
δ (q0 , d, ε) = (q0 , d)
δ (q0 , c, ε) = (q1 , ε)
δ (q1 , d, d) = (q1 , ε)
δ (q1 , ε, ε) = (q2 , ε)

kr chowdhary

d, d/ε
c, ε/ε

q1

ε, ε/ε

q2

Note that we have not included the
transitions corresponding to first
writing Z0 on stack and finally
retrieving it back. This is
acceptable as PDA is
non-deterministic.

TOC

6/ 8

PDA moves
PDA moves
1. (q, x, α) ⊢∗ (q ′ , ε, β ) ⇒ (q, xy , α) ⊢∗ (q ′ , y , β )

2. (q, xy , α) ⊢∗ (q ′ , y , β ) ⇒ (q, xy , αγ) ⊢∗ (q ′ , y , β γ)

The case 1., above is obvious, however, the case 2., is not
guaranteed due to the trace of computation shown below.

kr chowdhary

TOC

7/ 8

Bibliography

Chowdhary, K.R. (2025). Pushdown Automata and Parsers. In:
Theory of Computation. Springer, Singapore.
https://doi.org/10.1007/978-981-97-6234-7_8

kr chowdhary

TOC

8/ 8