Pushdown Automata(PDA)

o Pushdown automata is a way to implement a CFG in the same way we design DFA
for a regular grammar. A DFA can remember a finite amount of information, but a
PDA can remember an infinite amount of information.
o Pushdown automata is simply an NFA augmented with an "external stack
memory". The addition of stack is used to provide a last-in-first-out memory
management capability to Pushdown automata. Pushdown automata can store an
unbounded amount of information on the stack. It can access a limited amount of
information on the stack. A PDA can push an element onto the top of the stack
and pop off an element from the top of the stack. To read an element into the
stack, the top elements must be popped off and are lost.
o A PDA is more powerful than FA. Any language which can be acceptable by FA can
also be acceptable by PDA. PDA also accepts a class of language which even
cannot be accepted by FA. Thus PDA is much more superior to FA.

PDA Components:
Input tape: The input tape is divided in many cells or symbols. The input head is read-
only and may only move from left to right, one symbol at a time.

Finite control: The finite control has some pointer which points the current symbol
which is to be read.

Stack: The stack is a structure in which we can push and remove the items from one
end only. It has an infinite size. In PDA, the stack is used to store the items temporarily.

A Pushdown Automata (PDA) can be defined as :

 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
 Z is the initial pushdown symbol (which is initially present in stack)

δ is a transition function which maps Q x {Σ ∪ ∈} x Γ into Q x Γ*. In a given state, PDA

 F is the set of final states

will read input symbol and stack symbol (top of the stack) and move to a new state and change the
symbol of stack.

Instantaneous Description (ID)

Instantaneous Description (ID) is an informal notation of how a PDA “computes” a
input string and make a decision that string is accepted or rejected.
A ID is a triple (q, w, α), where:
1. q is the current state.
2. w is the remaining input.
3.α is the stack contents, top at the left.

⊢ sign is called a “turnstile notation” and represents one move.

Turnstile notation

⊢* sign represents a sequence of moves.

Eg- (p, b, T) ⊢ (q, w, α)
This implies that while taking a transition from state p to state q, the input symbol ‘b’ is
consumed, and the top of the stack ‘T’ is replaced by a new string ‘α’

Example 1: Construct a PDA for language L = {wcw R | w={0, 1}*} where w R is the reverse
of w.
(OR)
Design a PDA that accepts the language of odd palindrome
Approach used in this PDA –
Keep on pushing 0’s and 1’s no matter whatever is on the top of stack until reach the middle
element c. When middle element ‘c’ is scanned then process it without making any changes in
stack. Now if scanned symbol is ‘1’ and top of stack also contain ‘1’ then pop the element from
top of stack or if scanned symbol is ‘0’ and top of stack also contain ‘0’ then pop the element
from top of stack. If string becomes empty or scanned symbol is z and stack becomes empty,
then reach to final state else move to dead state.
Step 1: On receiving 0 or 1, keep on pushing it on top of stack without going to next state.
Step 2: On receiving an element ‘c’, move to next state without making any change in stack.
Step 3: On receiving an element, check if symbol scanned is ‘1’ and top of stack also contain
‘1’ or if symbol scanned is ‘0’ and top of stack also contain ‘0’ then pop the element from top of
stack else move to dead state. Keep on repeating step 3 until string becomes empty.
Step 4: Check if symbol scanned is ‘∈’ and stack does not contain any element then move to
final state else move to dead state.

δ( q0, ∈, z) = { ( q0, z) }
δ is given by :

δ( q0, 0, z ) = { ( q0, 0z ) }

δ( q0, 0, 0) = { ( q0, 00) }

δ( q0, 1, z) = { ( q0, 1z ) }

δ( q0, 1, 1) = { ( q0, 11) }

δ( q0, 1, 0) = { ( q0, 10) }
δ( q0, 0, 1) = { ( q0, 01) }
δ( q0, c, 1) = { ( q1, 1) }
δ( q0, c, 0) = { ( q1, 0) }
δ( q0, c, z) = { ( q1, z) }
δ( q1, 1, 1) = { ( q1, z) }
δ( q1, 0, 0) = { ( q1, z) }
δ( q1, ∈, z) = { ( q2, z) }
Let us see how this automata works for 001c100.

Unread Transition Stack New state

Input
001c100 ------ z q0
01c100 (q0,0,z,push(0) 0z q0
,q0)
1c100 (q0,0,0,push(0 00z q0
),q0)
c100 (q0,1,0,push(1 100z q0
),q0)
100 (q0,c,1,nop,q1) 100z q1
00 (q1,1,1,pop,q1 00z q1
)
0 (q1,0,0,pop,q1 0z q1
)
∈
0,0,pop,q1)
(q1, z q1

------
∈,z,nop,q2)
(q1, z q2

i) Toshow that w=001c100 is accepted by PDA is,

ID for 001c100 is
(q0,001c100,z)
⊢(q0,01c100,0z)
⊢(q0,1c100,00z)
⊢(q0,c100,100z)
⊢(q1,100,100z)
⊢(q1,00,00z)
⊢(q1, 0,0z)
⊢(q1, ∈,z)
⊢(q2, z)
ACCEPT
ii) Toshow that w=01c100 is rejected by PDA is,
ID for 01c100 is
(q0,01c100,z)
⊢(q0,1c100,0z)
⊢(q0,c100,10z)
⊢(q1,00,10z)
Example 2:
Construct a PDA for language L = {ww R | w={0, 1}*} where w R is the reverse of w.
(OR)
Design a PDA that accepts the language of even palindrome
Approach used in this PDA –

For construction of even length palindrome, user has to use Non Deterministic Pushdown
Automata (NPDA).
A NPDA is basically an NFA with a stack added to it.
The NPDA for this language is identical to the previous one except for epsilon transition.
However, there is a significant difference, that this PDA must guess when to stop pushing
symbols, jump to the final state and start matching off of the stack.
Therefore this machine is decidedly non-deterministic.
Keep on pushing 0’s and 1’s no matter whatever is on the top of stack and at the same time
keep a check on the input string, whether reach to the second half of input string or not.
If reach to last element of first half of the input string then after processing the last element of
first half of input string make an epsilon move and move to next state.
Now if scanned symbol is ‘1’ and top of stack also contain ‘1’ then pop the element from top of
stack or if scanned symbol is ‘0’ and top of stack also contain ‘0’ then pop the element from top
of stack.
If string becomes empty or scanned symbol is ‘∈’ and stack becomes empty, then reach to
final state else move to dead state.

Step 1: On receiving 0 or 1, keep on pushing it on top of stack and at a same time keep on
checking whether reach to second half of input string or not.

Step 2: If reach to last element of first half of input string, then push that element on top of
stack and then make an epsilon move to next state.

Step 3: On receiving an element, check if symbol scanned is ‘1’ and top of stack also contain
‘1’ or if symbol scanned is ‘0’ and top of stack also contain ‘0’ then pop the element from top of
stack else move to dead state. Keep on repeating step 3 until string becomes empty.

Step 4: Check if symbol scanned is ‘∈’ and stack does not contain any element then move to
final state else move to dead state.

δ is given by :
δ( q0, 0, z ) = { ( q0, 0z ) }

δ( q0, 0, 0) = { ( q0, 00) }

δ( q0, 1, z) = { ( q0, 1z ) }

δ( q0, 1, 1) = { ( q0, 11) }

δ( q0, 1, 0) = { ( q0, 10) }
δ( q0, 0, 1) = { ( q0, 01) }
δ( q0, ∈, z) = { ( q1, z) }
δ( q1, 1, 1) = { ( q1, z) }
δ( q1, 0, 0) = { ( q1, z) }
δ( q1, ∈, z) = { ( q2, z) }

Let us see how this automata works for 001100.

Unread Transition Stack New state
Input
001100 ------ z q0
01100 (q0,0,z,push(0) 0z q0
,q0)
1100 (q0,0,0,push(0 00z q0
),q0)
100 (q0,1,0,push(1 100z q0
),q0)
100 (q0, ∈ 100z q1
,1,nop,q1)
00 (q1,1,1,pop,q1 00z q1
)
0 (q1,0,0,pop,q1 0z q1
)
∈
0,0,pop,q1)
(q1, z q1

------
∈,z,nop,q2)
(q1, z q2

Toshow that w=001100 is accepted by PDA is,

ID for 001100 is
(q0,001100,z)
⊢(q0,01100,0z)
⊢(q0,1100,00z)
⊢(q0,100,100z)
⊢(q1,100,100z)
⊢(q1,00,00z)
⊢(q1, 0,0z)
⊢(q1, ∈,z)
⊢(q2, z)
Example 3:
Define the pushdown automata for language {anbn | n > 0}

Solution : M ={Q, Σ, Γ, q0, z, δ, F}

where Q = { q0, q1 } and Σ = { a, b } and Γ = { a,b, z }
Design Strategy :
Initially, the state of automata is q0 and symbol on stack is Z and the input is
aaabbb as shown in row 1.
On reading ‘a’ the state will remain q0 and it will push symbol a on stack.
On next ‘a’, it will push another symbol a on stack.
After reading 3 a’s, the stack will be aaaz with a on the top.
After reading ‘b’, it will pop a and move to state q1 and stack will be aaz.
When all b’s are read, the state will be q1 and stack will be z.
On input symbol ‘∈’ and z on stack, and nop and stack with z.
This type of acceptance is known as acceptance by empty stack.

δ is given by :
δ( q0, a, z ) = { ( q0, az ) }

δ( q0, b, a) = { ( q1, ∈) }
δ( q0, a, a) = { ( q0, aa ) }

δ( q1, b, b) = { ( q1, ∈) }
δ( q1, ∈, z) = { ( q2, ∈) }

Let us see how this automata works for aaabbb.

Unread Transition Stack New state
Input
aaabbb ------ z q0
aabbb (q0,a,z,push(a az q0
),q0)
abbb (q0,a,a,push(a aaz q0
),q0)
bbb (q0,a,a,push(a aaaz q0
),q0)
bb (q0,b,a,pop,q1 aaz q1
)
b (q1,b,a,pop,q1 az q1
)
∈ (q1,b,a,pop,q1 z q1
)
------
∈,z,nop,q2)
(q1, z q2

ID for aaabbb is
(q0,aaabbb,z)
⊢(q0,aabbb,az)
⊢(q0,abbb,aaz)
⊢(q0,bbb,aaaz)
⊢(q1,bb,aaz)
⊢(q1,b,az)
⊢(q1, ∈,z)
⊢(q2,z)
Note :
 The above pushdown automaton is deterministic in nature because there is only
one move from a state on an input symbol and stack symbol.
 The non-deterministic pushdown automata can have more than one move from a
state on an input symbol and stack symbol.
 It is not always possible to convert non-deterministic pushdown automata to
deterministic pushdown automata.
 Expressive Power of non-deterministic PDA is more as compared to expressive
deterministic PDA as some languages which are accepted by NPDA but not by
deterministic PDA which will be discussed in next article.
 The push down automata can either be implemented using accepetance by
empty stack or accepetance by final state and one can be converted to another.

Example 4:
Design a PDA for accepting a language {a2nbn | n>=1}.

Solution: In this language, 2n number of a's should be followed by n number of b's.

Hence, for first a we will push a onto the stack and for second a we will do nop , and if
we read 'b', we will pop a from the stack. Hence for every single 'b' one 'a' should get
popped from the stack.

The δ can be as follows:

δ(q0, a, z) = (q0, az)
δ(q0, a, a) = (q1, az)
δ(q1, a, a) = (q0, aa)

δ(q1, b, a) = (q2, ∈)
δ(q0, a, a) = (q1, aa)

δ(q2, b, a) = (q2, ∈)
δ(q2, ∈ , z) = (q3, ∈)
Let us see how this automata works for aaaabb.

Unread Transition Stack New state

Input
aaaabb ------ z q0
aaabb (q0,a,a,push(a az q0
),q0)
aabb (q0,a,a,nop,q1 az q1
)
abb (q1,a,a,push(a aaz q0
),q0)
bb (q0,a,a,nop,q1 aaz q1
)
b (q1,b,a,pop,q2 az q2
)
∈ (q2,b,a,pop,q2 z q2
)
------
∈,z,nop,q3)
(q2, z q3

ID for aaaabb is

⊢(q0,aaabb,az)
(q0,aaaabb,z)

⊢(q1,aabb,az)
⊢(q0,abb,aaz)
⊢(q1,bb,aaz)
⊢(q1,b,az)
⊢(q1, ∈,z)
⊢(q2,z)
Example 5:
Design a PDA for accepting a language {0n1m0n | m, n>=1}.

Solution: In this PDA, n number of 0's are followed by m number of 1's followed n
number of 0's. Hence the logic for design of such PDA will be as follows:

Push all 0's onto the stack on encountering first 0's. Then if we read 1, just do nothing.
Then read 0, and on each read of 0, pop one 0 from the stack.

The δ can be as follows:

δ(q0, 0, Z) = δ(q0, 0Z)
δ(q0, 0, 0) = δ(q0, 00)
δ(q0, 1, 0) = δ(q1, 0)
δ(q1, 1, 0) = δ(q1, 0)
δ(q1, 0, 0) = δ(q2, ε)
δ(q2, 0, 0) = δ(q2, ε)
δ(q2, ε, Z) = δ(q3, Z) (ACCEPT state)

Let us see how this automata works for 0011100.

Unread Transition Stack New state

Input
0011100 ------ z q0
011100 (q0,0,z,push(0) 0z q0
,q0)
11100 (q0,0,0,push(0 00z q0
),q0)
1100 (q0,1,0,nop,q1 00z q1
)
100 (q1,1,0,nop,q1 00z q1
)
00 (q1,1,0,nop,q1 00z q1
)
0 (q1,0,0,pop,q2 0z q2
)
∈
0,0,pop,q2)
(q2, z q2

--------
∈,z,nop,q3)
(q2, z q3

Now we will simulate this PDA for the input string "0011100".
ID is

δ(q0, 0011100, Z) ⊢ δ(q0, 011100, 0Z)

⊢ δ(q0, 11100, 00Z)

⊢ δ(q1, 1100, 00Z)
⊢ δ(q1, 100, 00Z)
⊢ δ(q1, 00, 00Z)
⊢ δ(q2, 0, 0Z)
⊢ δ(q2, ε, Z)
⊢ δ(q3, Z)

Example 6:
Construct a PDA that accepts the language L over {0, 1} by empty stack which
accepts all the string of 0's and 1's in which a number of 0's are twice of
number of 1's.

Solution:

There are two parts for designing this PDA:

o If 1 comes before any 0's

o If 0 comes before any 1's.

We are going to design the first part i.e. 1 comes before 0's. The logic is that read 1’s
and push onto the stack. For every 1 we have two 0’s. For first part of 0’s pop 1 and for
second part of 0’s we are not doing any operation.

The δ can be as follows:

δ(q0, 1, Z) = (q0, 1Z)
δ(q0, 1, 1) = (q0, 11)
δ(q0, 0, 1) = (q1, 1)
δ(q1, 0, 1) = (q1, z)
δ(q1, 0, z) = (q2, z)
δ(q2, 0, z) = (q2, z)
δ(q2, ε, z) = (q3, z)

1n02n
Now, consider the second part i.e. if 0 comes before 1's. The logic is that read first 0
push it onto the stack and for second 0 we are not doing any operation. Whenever we
see 1’s we pop all 0’s from the stack.

The δ can be as follows:

δ(q0, 0, Z) = (q0, 0Z)
δ(q0, 0, 0) = (q4, 0)
δ(q4, 0, 0) = (q0, 00)
δ(q4, 1, 0) = (q5, z)
δ(q5, 1, 0) = (q5, z)
δ(q5, ε, z) = (q3, z)

02n1n

Now, summarize the complete PDA for given L is:

The δ can be as follows:

δ(q0, 1, Z) = (q0, 1Z)
δ(q0, 1, 1) = (q0, 11)
δ(q0, 0, Z) = (q0, 0Z)
δ(q0, 0, 0) = (q4, 0)
δ(q0, 0, 1) = (q1, 1)
δ(q1, 0, 1) = (q1, z)
δ(q1, 0, z) = (q2, z)
δ(q2, 0, z) = (q2, z)
δ(q2, ε, z) = (q3, z)
δ(q4, 0, 0) = (q0, 00)
δ(q4, 1, 0) = (q5, z)
δ(q5, 1, 0) = (q5, z)
δ(q5, ε, z) = (q3, z)
Let us see how this automata works for 000011

Unread Transition Stack New state

Input
000011 ------ z q0
00011 (q0,0,z,push(0), 0z q0
q0)
0011 (q0,0,0,nop,q4) 0z q4
011 (q4,0,0, 00z q0
push(0),q0)
11 (q0,0,0,nop,q4) 00z q4
1 (q4,1,0,pop,q5) 0z q5
∈ (q5,1,0,pop,q5) z q5
-------- (q5, ∈,z,nop,q3) z q3

Now we will simulate this PDA for the input string "000011".

δ(q0, 000011, Z) ⊢ δ(q0, 00011, 0Z)

⊢ δ(q4, 0011, 0Z)
⊢ δ(q0, 011, 00Z)
⊢ δ(q4, 11, 00Z)
⊢ δ(q5, 1, 0Z)
⊢ δ(q5, ∈, Z)
⊢ δ(q3, Z)
Home Work String 110000

Do the transition table and ID for the above string

PDA Acceptance
A language can be accepted by Pushdown automata using two approaches:

1. Acceptance by Final State: The PDA is said to accept its input by the final state if it
enters any final state in zero or more moves after reading the entire input.

Let P =(Q, ∑, Γ, δ, q0, Z, F) be a PDA. The language acceptable by the final state can be
defined as:

L(PDA) = {w | (q0, w, Z) ⊢* (p, ε, ε), q ∈ F}

2. Acceptance by Empty Stack: On reading the input string from the initial
configuration for some PDA, the stack of PDA gets empty.

Let P =(Q, ∑, Γ, δ, q0, Z, F) be a PDA. The language acceptable by empty stack can be
defined as:

N(PDA) = {w | (q0, w, Z) ⊢* (p, ε, ε), q ∈ Q}

Equivalence of Acceptance by Final State and Empty Stack
If L = N(P1) for some PDA P1, then there is a PDA P2 such that L = L(P2). That
means the language accepted by empty stack PDA will also be accepted by final
state PDA.

If there is a language L = L (P1) for some PDA P1 then there is a PDA P2 such that
L = N(P2). That means language accepted by final state PDA is also acceptable by
empty stack PDA.

Example 7:
Design PDA that accepts the language L over {a, b, c} by acceptance by final
state where L={a3bncn / n>0}

Soln:

Here ensure that exactly 3 a’s are read initially. Then read all b’s on to the stack and
match them with c’s by popping off. To ensure three a’s, read each a and change state.

δ(q0, a, Z) = (q1, Z)
δ(q1, a, z) = (q2, z)
δ(q2, a, Z) = (q3, Z)
δ(q3, ε, z) = (qf, z)
δ(q3, b, z) = (q4, bz)
δ(q4, b, b) = (q4, bb)
δ(q4, c, b) = (q5, z)
δ(q5, c, b) = (q5, z)
δ(q5, ε, z) = (qf, z)

Let us see how this automata works for ‘aaabbcc’

Unread Transition Stack New state

Input
aaabbcc ------ z q0
aabbcc (q0,a,z, nop,q1) z q1
abbcc (q1,a,z,nop,q2) z q2
bbcc (q2,a,z, nop,q3) z q3
bcc (q3,b,z,push(b), bz q4
q4)
cc (q4,b,b,push(b), bbz q4
q4)
c (q4,c,b,pop,q5) bz q5
 ∈ (q5, c,b,pop,q5) z q5
--------- (q5, ∈,z,nop,qf) z qf

Now we will simulate this PDA for the input string "aaabbcc".

δ(q0, aaabbcc, Z) ⊢ δ(q1, aabbcc, Z)

⊢ δ(q2, abbcc, Z)
⊢ δ(q3, bbcc, Z)
⊢ δ(q4, bcc, bZ)
⊢ δ(q4, cc, bbZ)
⊢ δ(q5, c, bZ)
⊢ δ(q5, ∈, Z)
⊢ δ(qf, Z)

Example 8: Design a PDA that accepts L = {anbmcmdn; n, m ≥ 1} accepted by empty

stack and check whether the string w = aaabcddd is accept or not.

CFG to PDA Conversion

The first symbol on R.H.S. production must be a terminal symbol. The following
steps are used to obtain PDA from CFG is:

Step 1: Convert the given productions of CFG into GNF.

Step 2: The PDA will only have one state {q}.

Step 3: The initial symbol of CFG will be the initial symbol in the PDA.

Step 4: For non-terminal symbol, add the following rule:

δ(q, ε, A) = (q, α)

Where the production rule is A → α

Step 5: For each terminal symbols, add the following rule:

δ(q, a, a) = (q, ε) for every terminal symbol

Example 1:
Construct PDA for the given CFG, and test whether 010 4 is acceptable
by this PDA.

S → 0BB
B → 0S | 1S | 0

Solution:
The PDA can be given as:

A = {(q), (0, 1), (S, B, 0, 1), δ, q, S, Φ}

The production rule δ can be:

R1: δ(q, ε, S) = {(q, 0BB)}

R2: δ(q, ε, B) = {(q, 0S) | (q, 1S) | (q, 0)}
R3: δ(q, 0, 0) = {(q, ε)}
R4: δ(q, 1, 1) = {(q, ε)}

Testing 0104 i.e. 010000 against PDA:

δ(q, 010000, S) ⊢ δ(q, 010000, 0BB) R1

⊢ δ(q, ε10000, BB) R3
⊢ δ(q, 10000,1SB) R2
⊢ δ(q, ε0000, SB) R4
⊢ δ(q, 0000, 0BBB) R1
⊢ δ(q, ε000, BBB) R3
⊢ δ(q, 000, 0BB) R2
⊢ δ(q, ε00, BB) R3
⊢ δ(q, 00, 0B) R2
⊢ δ(q, ε0, B) R3
⊢ δ(q, 0, 0) R2
⊢ δ(q, ε) R3
ACCEPT

Thus 0104 is accepted by the PDA.

Example 2:
Draw a PDA for the CFG given below:

S → aSb
S→a|b|ε

Solution:

The PDA can be given as:

P = {(q), (a, b), (S, a, b, z0), δ, q, z0, q}

The mapping function δ will be:

R1: δ(q, ε, S) = {(q, aSb)|(q, a) | (q, b) | (q, ε)}

R2: δ(q, a, a) = {(q, ε)}
R3: δ(q, b, b) = {(q, ε)}
R4: δ(q, ε, z0) = {(q, ε)}

Simulation: Consider the string aaabb

δ(q, aaabb, S) ⊢ δ(q, aaabb, aSb) R1
⊢ δ(q, εaabb, Sb) R2
⊢ δ(q, aabb, aSbb) R1
⊢ δ(q, εabb, Sbb) R2
⊢ δ(q, abb, abb) R1
⊢ δ(q, bb, bb) R2
⊢ δ(q, b, b) R3
⊢ δ(q, ε, z0) R4
⊢ δ(q, ε)
ACCEPT
Example 3:
Construct a PDA from the following CFG.G = ({S, A}, {a, b}, P, S) where the productions are
S → AS / ε
A → aAb / Sb / a
Solution:
Let the equivalent PDA, M = ({q}, {a, b}, {a, b, A, S}, δ, q, S)
where δ:
R1:δ(q, ε , S) = {(q, AS), (q, ε )}
R2: δ(q, ε , A) = {(q, aAb), (q, Sb), (q, a)}
R3: δ(q, a, a) = {(q, ε )}
R4: δ(q, b, b) = {(q, ε )}

Example 4: Consider the grammar G = (V, T, P, S) with V = {S}, T = {a, b, c}, and
P = {S → aSa, S → bSb, S → c}

Solution:
Let the equivalent PDA, M = ({q}, {a, b, c}, {a, b, c, S}, δ, q, S)
where δ:
R1: δ(q, ε , S) = {(q, aSa), (q, bSb ), (q,c )}
R 2 : δ(q, a, a) = {(q,
ε )}
R3:δ(q, b, b) = {(q, ε )}
R4: δ(q, c, c) = {(q, ε )}

Example 5: Consider the grammar G = (VN, VT, P, S) with P = { S → abA / baA / B / ε ,

A→ bS / b, B → aS, C → ε}
Solution:
Let the equivalent PDA, M = ({q}, {a, b}, {a, b, S, A, B, C}, δ, q, S)
where δ:
R1: δ(q, ε , S) = {(q, abA), (q, baA ), (q, B ), (q, ε )}
R 2 : δ(q, ε , A) = {(q, bS), (q,
b)}
R3: δ(q, ε , B) = {(q, aS)}
R4: δ(q, ε , C) = {(q, ε )}
R5: δ(q, a, a) = {(q, ε )}
R6: δ(q, b, b) = {(q, ε )}
Example 6: Consider the grammar G = (VN, VT, P, S) Where P : S → A / B / ε A → 0S/1B/0
B → 0S/1A/1

Solution:
Let the equivalent PDA, M = ({q}, {0, 1}, {0, 1, S, A, B}, δ, q, S)
where δ:
R1: δ(q, ε , S) = {(q, A), (q, B ), (q, ε )}
R2: δ(q, ε , A) = {(q, 0S), (q, 1B), (q, 0)}
R3: δ(q, ε , B) = {(q, 0S), (q, 1A), (q, 1)}
R 4 : δ(q, 0, 0) = {(q, ε )}
R5: δ(q, 1, 1) = {(q, ε )}

Example 7: Construct a PDA that will accept the language generated by the grammar G = ({S, A},
{a, b}, P, S) with the productions S → AA / a, A → SA / b and test whether “abbabb” is in N(M).

Solution:
Let the equivalent PDA, M = ({q}, {a, b}, {a, b, S, A}, δ, q, S)
where δ:
R1: δ(q, ε , S) = {(q, AA), (q, a }
R2: δ(q, ε , A) = {(q, SA), (q, b)}
R3: δ(q, a, a) = {(q, ε )}
R4: δ(q, b, b) = {(q, ε )}

δ(q, abbabb , S) ⊢ δ(q, abbabb , AA)

Test whether “abbabb” is in N(M):

⊢ δ(q, abbabb , SAA)

R1

⊢ δ(q, abbabb , aAA)

R2

⊢ δ(q, εbbabb , AA)

R1

⊢ δ(q, bbabb , SAA)

R3

⊢ δ(q, bbabb , AAAA)

R2

⊢ δ(q, bbabb , bAAA)

R1

⊢ δ(q, εbabb , AAA)

R2

⊢ δ(q, babb , bAA)

R4

⊢ δ(q, εabb , AA)

R2

⊢ δ(q, abb , SAA)

R4

⊢ δ(q, abb , aAA)

R2

⊢ δ(q, εbb , AA)

R1

⊢ δ(q, bb , bA)
R3

⊢ δ(q, εb , A)
R2

⊢ δ(q, b , b)
R4

⊢ δ(q, ε , ε)
R2
R4

Tutorial Problems:

1. Consider the grammar G = (VN, VT, P, S) and test whether “abbabb” is in N(M).
Where P :
S → abA / baA / B / ε
A→ bS / b
 B→ S
C→ε
2. Consider the grammar G = (V, T, P, S)
Where P :
A → aB
B → aB/bB/ε
3. Consider the grammar G = (V, T, P, S) and test whether “0101001” is in N(M). Where P :
S → 0S/1A/1/0B/0
A → 0A/1B/0/1
B → 0B/1A/0/1
4. Consider the grammar G = (V, T, P, S)
Where P :
A → Ba/Ab/b
B → Ca/Bb
C → Aa/Cb/a
5. Consider the grammar G = (V, T, P, S)
Where P :
A → aB/bA/b
B → aC/bB
C → aA/bC/a
6. Consider the grammar G = (V, T, P, S)
Where P :
S → ABCD
A → aab
B → bba / bbaB
C → bab
D → aab / aabD

Construction of CFL equivalent to PDA

If M=(Q, ∑, Γ, δ, q0, Z, F) is a PDA, then there exists a CFG, G such that L(G)=N(M)

L(G) is CFL.

Procedure: Construction of G.
We define, G=(V,T,P,S)

V={S} U {[q,z,q’]/q,q’ ∈ Q, Z ∈ Γ}
Where,

Here,
S -> start symbol for G
q, q’ -> states
z -> push down symbol
The productions in P are induced by moves of PDA as follows:
R1: S productions are given by S → [q0,Z, q] for every qQ
For example:
We have two states (q0, q1), so two rules for starting variable.
S → [q0,Z,q0]
S → [q0 ,Z, q1]
R2: Each moves erasing a push down symbol given by (q’, ∈) ∈ δ(q, a, Z) induces the
production
[q Z q’] → a

R3: Each move non-erasing a push down symbol given by (q’ Z1 Z2 Z3…. Zn) ∈ δ(q,
a, Z) induces many productions of forms
[q Z q’] → a [q1 Z1 q2] [q2 Z2 q3]……[qn Zn q’]
Where each of states q1, q2, …. qn can be any state in Q

1. Convert the PDA P= ({q0, q1},{0,1},{X,Z0}, δ, q0 ,Φ, Z0) to a CFG , if is given by

1. δ(q0, 1, Z0) ={( q0, XZ0)}
2. δ(q0, 1, X) = {( q0, XX)}
3. δ(q0, 0, X) = {( q1, X)}
4. δ(q0, ε, X) = {( q0, ε)}
5. δ(q1, 1, X) = {( q1, ε)}
6. δ(q0, 0, Z0) = {( q1, Z0)}

Solution:
Step 1: Find the push and pop operations:
1. δ(q0, 1, Z0) ={( q0, XZ0)} - Push
2. δ(q0, 1, X) = {( q0, XX)} - Push
3. δ(q0, 0, X) = {( q1, X)} - Push
4. δ(q0, ε, X) = {( q0, ε)} - Pop
5. δ(q1, 1, X) = {( q1, ε)} - Pop
6. δ(q0, 0, Z0) = {( q1, Z0)} - Push

Step 2: Rules for start symbol:

We have two states q0 and q1. So, S productions are
1. S → [q0 Z0 q0] ------------ Eliminate
2. S → [q0 Z0 q1]

Step 3: Rules for POP operations:

Rules for δ(q0, ε, X) = {( q0, ε)} --- (4)
3. [q0 X q0] → ε

Rules for δ(q1, 1, X) = {( q1, ε)} --- (5)

4. [q1 X q1] → 1

Step 4: Rules for PUSH operations:

Rules for δ(q0, 1, Z0) ={( q0, XZ0)} --- (1)

5. [q0 Z0 q0] → 1 [q0 X q0] [q0 Z0 q0] -----------Eliminate

6. [q0 Z0 q1] → 1 [q0 X q0] [q0 Z0 q1] ----------Eliminate

7. [q0 Z0 q0] → 1 [q0 X q1] [q1 Z0 q0] ----------Eliminate

8. [q0 Z0 q1] → 1 [q0 X q1] [q1 Z0 q1]

Rules for δ(q0,1, X) = {( q0,XX)} --- (2)

9. [q0 X q0] → 1 [q0 X q0] [q0 X q0] ----------- Eliminate
10. [q0 X q1] → 1 [q0 X q0] [q0 X q1] ------ Eliminate
 11. [q0 X q0] → 1 [q0 X q1] [q1 X q0] --------- Eliminate
12. [q0 X q1] → 1 [q0 X q1] [q1 X q1]

Rules for δ(q0,0, X) = {( q1,X)} --- (3)

13. [q0 X q0] → 0 [q1 X q1] -------- Eliminate
14. [q0X q1] → 0 [q1 X q1]

Rules for δ(q0, 0, Z0) = {( q1, Z0)} --- (6)

15. [q0 Z0 q0] → 0 [q1 Z0 q0] ------- Eliminate
16. [q0 Z0 q1] → 0 [q1 Z0 q1]

Productions for the variables [q1 z0 q0] and [q1 x q0] and productions for [q0 z0 q0] and [q0 x q0]
do not exist. Deleting all productions involving these four variables on either the right or left
and we end up with the following productions.
1. S → [q0 Z0 q1]
2. [q0 X q0] → ε
3. [q1 X q1] → 1
4. [q0 Z0 q1] → 1 [q0 X q1] [q1 Z0 q1]
5. [q0 X q1] → 1 [q0 X q1] [q1 X q1]
6. [q0 X q1] → 0 [q1 X q1]
7. [q0 Z0 q1] → 0 [q1 Z0 q1]

2. Give the grammar for the language N(M) where M=({ q0 ,q1}, {0,1}, {X,Z0}, δ, q0, Z0, Φ) and δ
is given by,

1. δ(q0, 0, Z0) ={( q0, XZ0)}

2. δ(q0, 1, X) = {( q1, ε)}
3. δ(q0, 0, X) = {( q0, XX)}
4. δ(q1, ε, X) = {( q1, ε)}
5. δ(q0, 1, X) = {( q1, ε)}
6. δ(q1, ε, Z0) = {( q1, ε)}

3. Give the grammar for the language N(M) where M=({ q0 ,q1}, {a,b}, {Z,Z0}, δ, q0, Z0, Φ) and δ
is given by,

1. δ(q0, b, Z0) ={( q0, ZZ0)}

2. δ(q0, ε, Z0) = {( q0, ε)}
3. δ(q0, b, Z) = {( q0, ZZ)}
4. δ(q0, a, Z) = {( q1, Z)}
5. δ(q1, b, Z) = {( q1, ε)}
6. δ(q1, a, Z0) = {( q0, Z0)