ITS64304 Tutorial – 5: PDA 1
Bachelor of Software Engineering (Hons)
Bachelor of Computer Science (Hons)
ITS64304: Theory of Computation
Tutorial – 5: PDA
Aim
The aim of this tutorial is to get familiar with Pushdown Automata. By the end of this tutorial you
should be able to analyze and design some simple PDAs for a given language specification. (Aligns
with Module Learning Outcome 2)
Taylor’s Graduate Capabilities (TGCs) developed
3.1 Pushdown Automata
Example
1) Let M be the PDA defined by
Q = {q0, q1, q2} Σ= {a, b} Γ = {A} Final States = {q1, q2}
(q0, a, λ) = {q0, A} (q1, λ, A) = {q1, λ}
(q0, λ, λ) = {q1, λ} (q2, b, A) = {q2, λ}
(q0, b, A) = {q2, λ} (q2, λ, A) = {q2, λ}
Give the state diagram of M
Solution
ITS64304 Tutorial – 5: PDA 2
2) Trace of the computations of the strings aab, abb and aba in M.
├ (q0, aab, λ)
├ (q0, ab, A)
├ (q0, b, AA)
├ (q2, λ, A)
├ (q2, λ, λ) accept
3) Give the language accepted by M in set notation.
{aibj | 0 ≤ j ≤ i}
Questions
1) Construct a PDA that accepts each of the following:
a) L = { anb2n | n > 0}
b) {aibjck | i = j or j = k}
c) The language { w {a, b}* : w has twice as many b’s as a’s}
d) The language {w {a, b}* : w = wR}
2) Construct a PDA for a language over {a, b} where the strings contain the same number of a’s
and b’s.
3) Construct a PDA for the language over {a, b} where if the strings have any b’s then all a’s
precede all the b’s.
Reflection
Why a PDA is more powerful than a FSA/FSM? Use your tutorial sheet to give your answers and
observations from this tutorial.
-oo0oo-
├ (q0, abb, λ)
├ (q0, bb, A)
├ (q2, b, λ) reject
├ (q0, aba, λ)
├ (q0, ba, A)
├ (q2, a, λ) reject