UNIT 4 : PUSHDOWN AUTOMATA (PDA)

❑ Definition, Language of PDA

❑ PDA as generator, decider and acceptor of CFG,

❑ Deterministic PDA

❑ Non-Deterministic PDA

❑ Application of PDA.

TCS : UNIT 4 1
UNIT 4 : PUSHDOWN AUTOMATA (PDA)
CHOMSKY HIERARCHY

TCS : UNIT 4 2
 PUSHDOWN AUTOMATA (PDA)
❖ Pushdown Automata is a finite automata with extra memory called stack which helps Pushdown
automata to recognize Context Free Languages.
❖ A Pushdown Automata (PDA) can be defined as ( represented by 7 elements or tuples):
P = (Q, Σ, Γ, δ, q0, Z0, F)
➢Q is the set of states
➢∑ is the set of input symbols
➢Γ is the set of pushdown symbols (which can be pushed and popped from stack)
➢ q0 is the initial state
➢ Z0 is the initial pushdown symbol (which is initially present in stack)
➢F is the set of final states
➢δ is a transition function which maps Q x {Σ ∪ ∈} x Γ into Q x Γ*
In a given state, PDA will read input symbol and stack symbol (top of the stack) and
move to a new state and change the symbol of stack.
TCS : UNIT 4 3
A Pushdown Automata (PDA) is a way to implement context-free Grammar in a similar way.
We design Finite Automata for Regular Grammar.
1. It is more powerful than FSM.
2. FSM has very limited memory but PDA has more memory.
3. PDA= Finite State Machine + Stack
This stack has infinite memory and that facilitates the higher power of Pushdown automata.
This helps PDA to behave more powerful than Finite-state Machine.
A Pushdown Automata has three Components: Є

1. An input tape
2. A finite Control Unit.
3. A stack with infinite size.

TCS : UNIT 4 4
 ASSIGNMENT 4: Q1
Example : Design the pushdown automata for language {an b2n | n > 0}
OR
Design the pushdown automata for language {0n 12n | n > 0}
Soln: language = L = {0n 12n | n > 0}
δ: Q x {Σ ∪ ∈} x Γ into Q x Γ*

0 0 1 1 1 1 Є

0
0
Initial
Z0
Symbol
Stack

TCS : UNIT 4 5
0 0 1 1 1 1 Є

0 δ = Q x {Σ ∪ ∈} x Γ into Q x Γ*
Z0 δ(q0, 0, Z0 ) ➔ ( q0, 0 Z0 )
δ(q0, 0, 0 ) ➔ ( q0, 0 0 )
δ(q0, 1, 0 ) ➔ ( q1, 0 )
δ(q1, 1, 0 ) ➔ ( q2, Є)
δ(q2, 1, 0 ) ➔ (q1, 0 )
δ(q2, Є, Z0 ) ➔ ( qf, Z0 )
Z0

TCS : UNIT 4 6
Example : Define the pushdown automata for language {an bn | n > 0}
OR
Define the pushdown automata for language {0n 1n | n > 0}
Soln: language = L = {an bn | n > 0}

a a a b b b Є

a
a a
a a
Initial Z0 Z0
Symbol

Stack

TCS : UNIT 4 7
δ = Q x {Σ ∪ ∈} x Γ into Q x Γ*

TCS : UNIT 4 8
 Example : Design the pushdown automata for language accepting equal number of a’s and b’s.
Soln: Symbols = (a, b) language = L = string contains number of a’s equal to number of b’s

a b a a b b b b a a Є

Here stack is used to store both a’s & b’s but it will store only
excess of a’s over b’s or excess of b’s over a’s as per input
string

b a b b a a a a b b Є

TCS : UNIT 4 9
 q 1, Z0 )

TCS : UNIT 4 10
Example : Define the pushdown automata for language

Soln: Symbols = (0, 1) language = L = string w contains number of 0’s equal to number of 1’s

0 1 0 0 1 1 Є

Solution same as previous problem

TCS : UNIT 4 11
 Example : Construct the pushdown automata for language
L(M) = { wcwR | w {a,b}* } where wR is reverse of w & c is a constant
Soln: Symbols = (a, b)
language = L = if w has n symbols then length of the string will be 2n + 1 such that first n
symbols should match with last n symbols in reverse order.

a b b c b b a Є

Hint: Some string will come followed by one 'c', followed by reverse of the string before 'c’.
So we get to know that 'c' will work as an alarm to starting popping STACK.
So we will pop every 'a' with 'a' and every 'b' with 'b’. b

STEPS: b
a
1. Initially every a's and b’s, push them into STACK till ‘c’ comes.
Z
2. When 'c' comes do nothing.
3. Starting popping STACK: 'a' for 'a' and 'b' for 'b'.
TCS : UNIT 4 12
Solution Explanation :

Lets see, how this DPDA is working: For example take one input string: "abbcbba"

•Scan string from left to right

•First input is 'a' and follow the rule:
on input 'a' and STACK alphabet Z, push the two 'a's into STACK as : (a,Z/aZ) and state will be q0
•Second input is 'b' and so follow the rule:
on input 'b' and STACK alphabet 'a', push the 'b' into STACK as : (b,a/ba) and state will be q0
•Third input is 'b' and so follow the rule:
on input 'b' and STACK alphabet 'b', push the 'b' into STACK as : (b,b/bb) and state will be q0
•Fourth input is 'c' and so follow the rule:
on input 'c' and STACK alphabet 'a' or 'b' and state q0, do nothing as : (c,b/b) and state will be q1
•Fifth input is 'b' and so follow the rule:
on input 'b' and STACK alphabet 'b' (state is q1), pop one 'b' from STACK as : (b,b/ε) and state will be q1
•Sixth input is 'b' and so follow the rule:
on input 'b' and STACK alphabet 'b' (state is q1), pop one 'b' from STACK as : (b,b/ε) and state will be q1
•Seventh input is 'a' and so follow the rule:
on input 'a' and STACK alphabet 'a' and state q1, pop one 'a' from STACK as : (a,a/ε) and state will remain q1
•We reached end of the string, so follow the rule:
on input ε and STACK alphabet Z, go to final state(qf) as : (ε, Z/Z)
TCS : UNIT 4 13
 δ(q0, a, Z) = (q0, aZ)
δ(q0, a, a) = (q0, aa)
δ(q0, b, Z) = (q0, bZ)
δ(q0, b, b) = (q0, bb)
δ(q0, a, b) = (q0, ab)
δ(q0, b, a) = (q0, ba)

// this is decision step

a b b c b b a Є
δ(q0, c, a) = (q1, a)
δ(q0, c, b) = (q1, b)
δ(q1, b, b) = (q1, ε)
δ(q1, a, a) = (q1, ε)
δ(q1, ε, Z) = (qf, Z)
TCS : UNIT 4 14
 DPDA & NPDA
DPDA: For every input with the current state, there is
only one move.
M = (Q,∑,Γ,q0, Z,F ,δ)
δ: Q *{∑∪∈}* Γ→Q*Γ

NPDA: For every input with the current state, We can

have multiple moves.
M = (Q,∑,Γ,q0, Z,F ,δ)
δ: Q*{∑∪∈}*Γ→2Q* Γ*

TCS : UNIT 4 15
Why NPDA is more powerful than DPDA?
➢ NDPA is more powerful than DPDA because we can add more transitions to it.
➢ It is possible for every language to add a transition.
➢ For some languages, we can construct DPDA there exist an NPDA but there are some
languages that are accepted by NPDA but are not by DPDA. This is said to be powerful when
it accepts more sets of languages than other automata.
➢ In fact, it is more powerful than DFA(Deterministic finite automata) and NFA(Non-
deterministic finite automata) also because, In the case of DFA and NFA, they are equivalent
in power. So for every language accepted by DFA there exist an NFA and Vice-Versa. There is
not any language for which we construct NFA but not DFA. Hence, we can’t convert NPDA to
DPDA always and we can convert NFA to equivalent DFA always.

TCS : UNIT 4 16
 NDPA(Non-deterministic Pushdown
S. No DPDA(Deterministic Pushdown Automata)
Automata)
1. It is less powerful than NPDA. It is more powerful than DPDA.
It is possible to convert every DPDA to a It is not possible to convert every NPDA to
2.
corresponding NPDA. a corresponding DPDA.

The language accepted by DPDA is a subset The language accepted by NPDA is not a
3.
of the language accepted by NDPA. subset of the language accepted by DPDA.

The language accepted by DPDA is called

DCFL(Deterministic Context-free Language) The language accepted by NPDA is called
4. which is a subset of NCFL(Non- NCFL(Non-deterministic Context-free
deterministic Context-free Language) Language).
accepted by NPDA.

TCS : UNIT 4 17
EXPRESSIVE POWER OF VARIOUS AUTOMATA:
The Expressive Power of any machine can be determined from the class or set of Languages accepted by
that particular type of Machine. Here is the increasing sequence of expressive power of machines :

As we can observe that FA is less powerful than any other machine. It is important to note that DFA
and NFA are of same power because every NFA can be converted into DFA and every DFA can be
converted into NFA .
The Turing Machine i.e. TM is more powerful than any other machine.
i) Finite Automata (FA) equivalence:
Finite Automata ≡ PDA with finite Stack ≡ TM with finite tape ≡ TM with unidirectional tape ≡ TM with
read only tape
(ii) Pushdown Automata (PDA) equivalence:
PDA ≡ Finite Automata with Stack
TCS : UNIT 4 18
(iii) Turing Machine (TM) equivalence:
Turing Machine ≡ PDA with additional Stack ≡ FA with 2 Stacks

The Applications of these Automata are given as follows:

1. Finite Automata (FA) –
•For the designing of lexical analysis of a compiler.
•For recognizing the pattern using regular expressions.
•For the designing of the combination and sequential circuits using Mealy and Moore Machines.
•Used in text editors.
•For the implementation of spell checkers.
2. Push Down Automata (PDA) –
•For designing the parsing phase of a compiler (Syntax Analysis).
•For implementation of stack applications.
•For evaluating the arithmetic expressions.
•For solving the Tower of Hanoi Problem.
TCS : UNIT 4 19
3. Linear Bounded Automata (LBA) –
•For implementation of genetic programming.
•For constructing syntactic parse trees for semantic analysis of the compiler.
4. Turing Machine (TM) –
•For solving any recursively enumerable problem.
•For understanding complexity theory.
•For implementation of neural networks.
•For implementation of Robotics Applications.
•For implementation of artificial intelligence.

TCS : UNIT 4 20