Pushdown Automata (PDA) in Computer Engineering
UNIT IV
PUSHDOWN AUTOMATA
Ms. Shital Pawar
Assistant Professor
Computer Engineering Department
Bharati Vidyapeeth’s College of Engineering for Women,
Pune
Pushdown Automata(PDA)
•
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.
•
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.
•
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.
Pushdown Automata(PDA)
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
Formal definition of PDA:
•
The PDA can be defined as a collection of 7 components:
Q:
the finite set of states
∑:
the input set
Γ:
a stack symbol which can be pushed and popped from the
stack
q0:
the initial state
Z:
a start symbol which is in Γ.
F:
a set of final states
δ:
mapping function which is used for moving from current
state to next state.
Instantaneous Description (ID)
•
ID is an informal notation of how a PDA computes an input
string and make a decision that string is accepted or rejected.
•
An instantaneous description is a triple (q, w, α) where:
q
describes the current state.
w
describes the remaining input.
α
describes the stack contents, top at the left.
•
Turnstile Notation:
⊢
sign describes the turnstile notation and represents one move.
⊢
* sign describes a sequence of moves.
•
For example,
(p, b, T)
⊢
(q, w, α)
In the above example, while taking a transition from state p to
q, the input symbol 'b' is consumed, and the top of the stack
'T' is represented by a new string α.
Example 1
Design a PDA for accepting a language {an
b
2n
| n>=1}.
Solution:
•
Let us consider the string aabbbb for given language
•
In this language, n number of a's should be followed by 2n number
of b's. Hence, we will apply a very simple logic, and that is if we
read single 'a', we will push two a's onto the stack. As soon as we
read 'b' then for every single 'b' only one 'a' should get popped
from the stack.
Push a’s
Pop all a’s
Reading all a’s and pushing a’s will be done at state q0
δ(q0, a, Z
0
) = (q0, aaZ
0
) Reading 1
st
a and pushing 2 a’s onto the stack
δ(q0, a, a) = (q0, aaa) Reading all remaining a’s and pushing 2 a’s for every a
Now when we read b, we will change the state from q0 to q1 and start popping
corresponding 'a'. Hence,
δ(q0, b, a) = (q1, ε) Reading 1
st
b and popping topmost a from stack
Thus this process of popping 'b' will be repeated unless all the symbols are read.
Note that popping action occurs in state q1 only.
δ(q1, b, a) = (q1, ε) Reading all remaining b’s and popping one ‘a’ for every b
After reading all b's, all the corresponding a's should get popped. Hence when
we read ε as input symbol then there should be nothing in the stack.
δ(q1, ε, Z
0
) = (q2, ε) popping Z
0
from stack
•
Now we will simulate this PDA for the input string "aaabbbbbb".
δ(q0, aaabbbbbb, Z
0
)
⊢
δ(q0, aabbbbbb, aaZ
0
)
⊢
δ(q0, abbbbbb, aaaaZ
0
)
⊢
δ(q0, bbbbbb, aaaaaaZ
0
)
⊢
δ(q1, bbbbb, aaaaaZ
0
)
⊢
δ(q1, bbbb, aaaaZ
0
)
⊢
δ(q1, bbb, aaaZ
0
)
⊢
δ(q1, bb, aaZ
0
)
⊢
δ(q1, b, aZ
0
)
⊢
δ(q1, ε, Z
0
)
⊢
δ(q2, ε)
ACCEPT
Example 2
Design a PDA for accepting a language {0n
1
m
0
n
| m, n>=1}.
Solution:
•
In this PDA, n number of 0's are followed by any 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.
•
This scenario can be written in the ID form as:
δ(q0, 0, Z
0
) = δ(q0, 0Z
0
) (Reading 1
st
0’s and pushing 0’s on stack)
δ(q0, 0, 0) = δ(q0, 00) (Reading all 0’s and pushing all 0’s on stack)
δ(q0, 1, 0) = δ(q1, 0) (Reading fist 1 and no operation on stack)
δ(q1, 1, 0) = δ(q1, 0) (Reading all remaining 1’s and no operation on stack)
δ(q1, 0, 0) = δ(q1, ε) (Reading last sequence of 0’s and popping all 0’s)
δ(q1, ε, Z
0
) = δ(q2, Z
0
) (ACCEPT state)
•
Now we will simulate this PDA for the input string "0011100".
δ(q0, 0011100, Z
0
)
⊢
δ(q0, 011100, 0Z
0
)
⊢
δ(q0, 11100, 00Z
0
)
⊢
δ(q0, 1100, 00Z
0
)
⊢
δ(q1, 100, 00Z
0
)
⊢
δ(q1, 00, 00Z
0
)
⊢
δ(q1, 0, 0Z
0
)
⊢
δ(q1, ε, Z
0
)
⊢
δ(q2, Z
0
)
ACCEPT
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, Z0
)
⊢
* (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
0
, F) be a PDA. The language acceptable by
empty stack can be defined as:
•
N(PDA) = {w | (q0, w, Z0
)
⊢
* (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 3
Let L= {a
n
b
n
c
m
d
m
| n,m >=1} fin PDA to accept the language L
Solution: Acceptance by empty stack
•
Push sequence of a’s onto the stack.
•
For every b input symbol ,pop(erase) ‘a ‘from stack.
•
Push sequence of c’s onto the stack.
•
For every d input symbol ,pop(erase) ‘C ‘from stack.
•
PDA can be written as:
δ(q
0
, a, Z
0
) =(q
0
, aZ
0
) (push first a)
δ(q
0
, a, a) =(q
0
, aa) (push all remaining a’s)
δ(q
0
, b, a) =(q
1
, ε) (erase ‘a’ for first b)
δ(q
1
, b, a) =(q
1
, ε) (erase all remaining a’s for remaining b’s)
δ(q
1
, c, Z
0
) =(q
2
, cZ
0
) (push first c)
δ(q
2
, c, c) =(q
2
, cc) (push all remaining c’s)
δ(q
2
, d, c) =(q
3
, ε) (erase ‘c’ for first d)
δ(q
3
, d, c) =(q
3
, ε) (erase all remaining c’s for remaining d’s)
δ(q
3
, ε, Z
0
) =(q
3
, ε) (acceptance by empty stack)
Transition diagram for acceptance through empty stack
Example 3
Let L= {a
n
b
n
c
m
d
m
| n,m >=1} fin PDA to accept the language L
Solution: Acceptance by final state
•
Push sequence of a’s onto the stack.
•
For every b input symbol ,pop(erase) ‘a ‘from stack.
•
Push sequence of c’s onto the stack.
•
For every d input symbol ,pop(erase) ‘c‘from stack.
•
PDA can be written as:
δ(q
0
, a, Z
0
) =(q
0
, aZ
0
) (push first a)
δ(q
0
, a, a) =(q
0
, aa) (push all remaining a’s)
δ(q
0
, b, a) =(q
1
, ε) (erase ‘a’ for first b)
δ(q
1
, b, a) =(q
1
, ε) (erase all remaining a’s for remaining b’s)
δ(q
1
, c, Z
0
) =(q
2
, cZ
0
) (push first c)
δ(q
2
, c, c) =(q
2
, cc) (push all remaining c’s)
δ(q
2
, d, c) =(q
3
, ε) (erase ‘c’ for first d)
δ(q
3
, d, c) =(q
3
, ε) (erase all remaining c’s for remaining d’s)
δ(q
3
,
ε
, Z
0
) = (q
4
,Z
0
) (Acceptance through final state)
Transition diagram for acceptance through final state
Example 4
{ L=a
i
b
j
c
k
| k>=0 and i+j =k}
i) Find PDA accepting through final state
ii) find PDA accepting through empty stack
Solution:
•
For every input symbol ‘a’ , symbol x is pushed onto the stack.
•
For every input symbol ‘b’ , symbol x is pushed onto the stack.
•
For every input symbol ‘c’ , symbol x is popped from the stack.
2.
PDA accepting through empty stack:
δ(q
0
, a, Z
0
) =(q
0
, xZ
0
) (Reading first ‘a ‘ and pushing one x on stack)
δ(q
0
, a, x) =(q
0
,xx) (Reading all remaining a’s and pushing x on stack)
δ(q
0
, b, x) =(q
1
,xx) (Reading first b and pushing one x on stack)
δ(q
1
, b, x) =(q
1
, xx) (Reading all remaining b’s and pushing x on stack)
δ(q
1
, c, x) =(q
2
,
ε
) (Reading first c and popping x from stack)
δ(q
2,
c, x) =(q
2
,
ε
) (Reading remaining c’s and popping x from stack)
δ(q
2,
ε
, Z
0
) =(q
2
,
ε
) (acceptance through empty stack)
Transition diagram
2. PDA accepting through final state:
δ(q
0
, a, Z
0
) =(q
0
, xZ
0
) (Reading first ‘a ‘ and pushing one x on stack)
δ(q
0
, a, x) =(q
0
,xx) (Reading all remaining a’s and pushing x on stack)
δ(q
0
, b, x) =(q
1
,xx) (Reading first b and pushing one x on stack)
δ(q
1
, b, x) =(q
0
, xx) (Reading all remaining b’s and pushing x on stack)
δ(q
1
, c, x) =(q
2
,
ε
) (Reading first c and popping x from stack)
δ(q
2,
c, x) =(q
2
,
ε
) (Reading remaining c’s and popping x from stack)
δ(q
2,
ε
, Z
0
) =(q
3
, Z
0
) (Acceptance through final state)
Transition Diagram
Example 5
Design PDA for accepting a language L={WcW
T
| W
ϵ
{a,b}*}Solution:
•
W
T
stands for reversal of string in w.
•
For given language set of strings will be odd length palindrome.
•
E.g. L = {aca, bcb, aacaa, abcba, bacab, abbcbba…..}•
Consider a string : abbcbba
q
0
q
0
q
0
q
0
q
1
q
1
q
1
q
1
q
2
•
Steps to design PDA for given language:
1.
Read a’s and push ‘a’ it on stack without considering topmost
stack symbol.
2.
Read b’s and push ‘b’ it on stack without considering topmost stack
symbol.
3.
Read ‘c’ without doing any stack operation.
4.
Matching a’s with pop operation (To match symbol ‘a’ pop symbol
‘a’)
5.
Matching b’s with pop operation (To match symbol ‘b’ pop symbol
‘b’)
•
PDA for given language is:
δ(q
0
, a, ε) =(q
0,
a) (reading ‘a’ and pushing ‘a ‘on stack)
δ(q
0
, b, ε) =(q
0,
b) (reading ‘b’ and pushing ‘b’ on stack)
δ(q
0
, c, ε) =(q
1,
ε) (reading ‘c’ without any stack operation)
δ(q
1
, a, a) =(q
1,
ε) (matching ‘a’ with ‘a’ and pooping ‘a’)
δ(q
1
,b, b) =(q
1,
ε) (matching ‘b’ with ‘b’ and pooping ‘a’)
δ(q
1
,ε, Z
0
) =(q
2,
Z
0
) (acceptance through final state)
Example 6
Design PDA for accepting set of all strings over{a,b} with an equalnumber of a’s and b’s. The string should be accepted by
1. Final state 2. Empty stack
Solution:
•
Stack will store excess a’s over b’s or excess b’s over a’s.
•
Consider input as: ababbaabba
a
b
a
b
b
a
a
b
b
a
•
There should be following possible cases:
1. Stack contains topmost symbol as Z
0
and input is a
δ(q
0
, a, Z
0
) =(q
0,
aZ
0
) (reading symbol ‘a’ and pushing ‘a’ on stack)
2. Stack contains topmost symbol as Z
0
and input is b
δ(q
0
, b, Z
0
) =(q
0,
bZ
0
) (reading symbol ‘b’ and pushing ‘b’ on stack)
3. Stack contains topmost symbol ‘a’ and input is a
δ(q
0
, a, a
) =(q
0,
aa) (reading ‘a’ and pushing ‘a’ on stack)
4. Stack contains topmost symbol ‘b’ and input is b
δ(q
0
, b, b
) =(q
0,
bb) (reading ‘b’ and pushing ‘b’ on stack)
5. Stack contains topmost symbol ‘a’ and input is b
δ(q
0
, b, a
) =(q
0,
ε
) (reading ‘b’ and popping ‘a’ from stack)
6. Stack contains topmost symbol ‘b’ and input is a
δ(q
0
, a, b
) =(q
0,
ε
) (reading ‘b’ and popping ‘a’ from stack)
•
PDA: For acceptance through empty stack
δ(q
0
, a, Z
0
) =(q
0,
aZ
0
)
δ(q
0
, b, Z
0
) =(q
0,
bZ
0
)
δ(q
0
, a, a
) =(q
0,
aa)
δ(q
0
, b, b
) =(q
0,
bb)
δ(q
0
, b, a
) =(q
0,
ε
)
δ(q
0
, a, b
) =(q
0,
ε
)
δ(q
0,
ε
, Z
0
) =(q
0,
ε
)
•
PDA: For acceptance through final state
δ(q
0
, a, Z
0
) =(q
0,
aZ
0
)
δ(q
0
, b, Z
0
) =(q
0,
bZ
0
)
δ(q
0
, a, a
) =(q
0,
aa)
δ(q
0
, b, b
) =(q
0,
bb)
δ(q
0
, b, a
) =(q
0,
ε
)
δ(q
0
, a, b
) =(q
0,
ε
)
δ(q
0,
ε
, Z
0
) =(q
1,
Z
0
)
Transition Diagram
Transition Diagram
Types of PDA
There are two types of Pushdown Automata:
1.
DPDA( Deterministic PDA)
2.
NPDA(Non- Deterministic PDA)
Example 1
Design PDA to check whether a given string over{a,b} ends in abbSolution:
•
String ending in abb forms a regular language and a regular
language is accepted by DFA.
•
PDA for regular language can be constructed in two steps:
1.
Design DFA.
2.
Convert the DFA into PDA by accepting no-stack operation to
every transition in DFA.
So, for resulting PDA
M=
({q0,
q
1,
q
2,
q
3
),{a, b},{z0
},
ẟ,
q
0,
z
0,
{q3
})
δ(q
0
, b, Z
0
) =(q
0,
Z
0
)
δ(q
0
, a, Z
0
) =(q
1,
Z
0
)
δ(q
1
, a, Z
0
) =(q
1,
Z
0
)
δ(q
1
, b, Z
0
) =(q
2,
Z
0
)
δ(q
2
, a, Z
0
) =(q
1,
Z
0
)
δ(q
2
, b, Z
0
) =(q
3,
Z
0
)
δ(q
3
, a, Z
0
) =(q
1,
Z
0
)
δ(q
3
, b, Z
0
) =(q
0,
Z
0
)
Example 2
Design PDA to check whether a given string over{a,b} havingsubstring abb
Solution:
1. Design DFA for given regular language
2. Convert DFA into PDA
So, for resulting PDA
M=
({q0,
q
1,
q
2,
q
3
),{a, b},{z0
},
ẟ,
q
0,
z
0,
{q3
})
δ(q
0
, b, Z
0
) =(q
0,
Z
0
)
δ(q
0
, a, Z
0
) =(q
1,
Z
0
)
δ(q
1
, a, Z
0
) =(q
1,
Z
0
)
δ(q
1
, b, Z
0
) =(q
2,
Z
0
)
δ(q
2
, a, Z
0
) =(q
1,
Z
0
)
δ(q
2
, b, Z
0
) =(q
3,
Z
0
)
δ(q
3
, a, Z
0
) =(q
3,
Z
0
)
δ(q
3
, b, Z
0
) =(q
3,
Z
0
)
Example 3
Design PDA for detection of odd palindrome over{a,b}Solution:
•
Odd length palindrome will be of form:
WaW
R
and
WbW
R
•
E.g: aba, bab, ababa, babab, bbabb, aabaa, ……
•
As palindrome is odd length middle character is either ‘a’ or ‘b’ and
first sequence of n characters will be equal to reverse of last
sequence of n characters.
•
Following are the steps to design PDA:
There is no way to find middle character in a string. So middle
character will be fixed non deterministically.
1. Push first sequence of n characters on stack where n is non
deterministic.
2. Match last half sequence of n characters with characters on stack by
using pop operation.
3. For middle character perform no operation on stack.
Note:
perform stack operations irrespective of topmost stack symbol.
1. Push first half sequence of n characters on stack.
δ(q
0
, a,
ε
) =(q
0
, a)
δ(q
0
, b,
ε
) =(q
0
, b)
2. For middle character perform no operation on stack.
δ(q
0
, a,
ε
) = (q
1
,
ε
)
δ(q
0
, b,
ε
) = (q
1
,
ε
)
3. For last half sequence of n characters perform matching of by pop
operation.
δ(q
1
, a, a
) =(q
1
,
ε
)
δ(q
1
, b, b) =(q
1
,
ε
)
4. Acceptance through empty stack
δ(q
1
,
ε
, Z
0
)= (q
1
,
ε
)
•
So, PDA is: Acceptance through empty stack
δ(q
0
, a,
ε
) = {(q0,
a), (q
1,
ε
)}
δ(q
0
, b,
ε
) ={(q0,
b) , (q
1,
ε
)}
δ(q
1
, a, a
) = (q
1
,
ε
)
δ(q
0
, b, b) = (q
1
,
ε
)
δ(q
1
,
ε
, Z
0
)= (q
1
,
ε
) (acceptance through empty stack)
•
Here, Q =
(q
0,
q
1
)
∑ = {a, b}Γ
= {a,b,z0
}
Start state = q
0
Initial stack symbol = Z
0
Example 4
Design PDA for detection of even palindrome over{a,b}Solution:
•
Odd length palindrome will be of form:
WW
R
.
•
E.g: aa, bb, abba, baab, bbbb, aaaa, ……
•
As palindrome is even length first sequence of n characters will be
equal to reverse of last sequence of n characters.
•
Following are the steps to design PDA:
There is no way to find middle position in a string. So middle
character will be fixed non deterministically.
1. Push first sequence of n characters on stack where n is non
deterministic.
2. Match last half sequence of n characters with characters on stack by
using pop operation.
1. Push first half sequence on n characters on stack
•
First symbol can be either a or b.
δ(q
0
, a, Z
0
) = (q
0
, aZ
0
) (Reading first symbol ‘a’ and pushing ‘a’ on stack)
δ(q
0
, b, Z
0
) = (q
0
, bZ
0
) (Reading first symbol ‘b’ and pushing ‘b’ on
stack)
•
Read first half sequence of n characters and push it on stack.
δ(q
0
, a, a
) = (q
0
, aa)
δ(q
0
, b, b
) = (q
0
, bb
)
δ(q
0
, b, a) = (q
0
, ba
)
δ(q
0
, a, b
) = (q
0
, ab
)
2. Read last half sequence of n characters and pop first half sequence from
stack.
•
For pop operation we will do state change.
•
In last half sequence of n characters first symbol may be either ‘a’ or ‘b’
δ(q
0
, a, a
) = (q
1
,
ε
) (Matching first a and popping a from stack)
δ(q
0
, b, b
) = (q
1
,
ε
) (Matching first b and popping b from stack)
•
Popping remaining a’s and b’s for matching last half sequence a’s and
b’s.
δ(q
1
, a, a
) = (q
1
,
ε
) (Matching ‘a’ and popping ‘a’ from stack)
δ(q
1
, b, b
) = (q
1
,
ε
) (Matching ‘b’ and popping ‘b’ from stack)
•
Acceptance through empty stack
δ(q
1
,
ε
, Z
0
) = (q
1
,
ε
)
So, PDA is:
δ(q
0
, a, Z
0
) = (q
0
, aZ
0
)
δ(q
0
, b, Z
0
) = (q
0
, bZ
0
)
δ(q
0
, a, a
) =[ (q
0
, aa) , (q
1
,
ε
) ]
δ(q
0
, b, b
) = [(q
0
, bb
) , (q
1
,
ε
) ]
δ(q
0
, b, a) = (q
0
, ba
)
δ(q
0
, a, b
) = (q
0
, ab
)
δ(q
1
, a, a
) = (q
1
,
ε
)
δ(q
1
, b, b
) = (q
1
,
ε
)
δ(q
1
,
ε
, Z
0
) = (q
1
,
ε
)
•
Here, Q =
(q
0,
q
1
)
∑ = {a, b}Γ
= {a,b,z0
}
Start state = q
0
Initial stack symbol =Z
0
Example 5
Design PDA for detection of palindrome over {a,b}Solution:
•
Palindrome can be of even length or odd length
•
PDA for palindrome is:
δ(q
0
, a, Z
0
) = { (q0
, aZ
0
) (q
1
, Z
0
) }
δ(q
0
, b, Z
0
) = (q
0
, bZ
0
) (q
1
, Z
0
)
δ(q
0
, a, a
) ={ (q0
, aa) , (q
1
,
ε
) , (q
1
, a) }
δ(q
0
, b, b
) = {(q0
, bb
) , (q
1
,
ε
) , (q
1
, b)}
δ(q
0
, b, a) = {(q0
, ba
) . (q
1
, a)}
δ(q
0
, a, b
) = (q
0
, ab
) , (q
1
, a)}
δ(q
1
, a, a
) = (q
1
,
ε
)
δ(q
1
, b, b
) = (q
1
,
ε
)
δ(q
1
,
ε
, Z
0
) = (q
1
,
ε
) (Acceptance through empty stack)
PDA and CFG
•
The class of language accepted by pushdown automata is exactly the class
of context-free-languages.
•
Following three classes of language are same:
1.
Context Free Language defined by CFG.
2.
Language accepted by PDA by empty stack.
3.
Language accepted by PDA by final state.
•
So, it is possible to find PDA for CFG.
•
It is possible to find CFG for PDA
CFG
PDA by
empty
stack
PDA by
final
state
Equivalence of PDA and CFG
CFG to PDA Conversion
•
The following steps are used to obtain PDA from CFG is:
•
Step 1:
Convert
the given productions of CFG into GNF.
•
Step 1:
The PDA will only have one state {q}.•
Step 2:
The initial symbol of CFG will be the initial symbol in the
PDA.
•
Step 3:
For non-terminal symbol, add the following rule:
δ(q, ε, A) = (q, α)
Where the production rule is A → α
•
Step 4:
For each terminal symbols, add the following rule:
δ(q, a, a) = (q, ε)
for
every terminal symbol
Example 1
Convert the following grammar to a PDA that accepts the same
language.
S → 0S1 | A A → 1A0 | S | ε
Solution:
•
The CFG can be first simplified by eliminating unit productions:
•
S → 0S1 | 1S0 | ε
•
Now we will convert this CFG to GNF:
•
S → 0SX | 1SY | ε
•
X → 1 Y → 0
•
The PDA can be:
δ(q, ε, S) = {(q, 0SX) | (q, 1SY) | (q, ε)} δ(q, ε, X) = {(q, 1)} δ(q, ε, Y) = {(q, 0)} δ(q, 0, 0) = {(q, ε)} δ(q, 1, 1) = {(q, ε)}•
M =({q} , {0,1} , { S, X, Y, 0,1} , δ, q, S, Ø)
Example 2
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 010
4
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 010
4
is accepted by the PDA.
Example 3
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), δ, q,S ,Ø
}
•
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, ε)}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, ε) R3
ACCEPT
Construction of CFG from PDA
•
We can find CFG (G) for any PDA (M) such that,
L(G) = L(M)
•
We can construct an equivalent CFG for a PDA.
•
For constructed CFG the variable will be of the form:
x
[p q] , where p, q
ϵ
Q and x
ϵ
Γ.
•
The PDA can be given by: M = { Q , ∑ , Γ , δ , q0
, Z,
Φ
} (Z is
stack symbol)
•
Then equivalent CFG is given by: G = (V, T, P, S) where,
x
•
V= {S, [p q] |p, q ϵ
Q and X
ϵ
Γ }
Applications of Pushdown Automata
•
PDA is a machine for CFL .
•
A string belonging to CFL can be recognized by PDA.
•
PDA is extensively used for parsing.
•
There are two types of parsing :
1.
Top down parsing.
2.
Bottom up parsing.
Pushdown Automata & Parsing
•
Parsing is used to derive a string using the production
rules of a grammar. It is used to check the acceptability of
a string. Compiler is used to check whether or not a
string is syntactically correct. A parser takes the inputs
and builds a parse tree.
•
A parser can be of two types −
•
Top-Down Parser
− Top-down parsing starts from the top
with the start-symbol and derives a string using a parse
tree.
•
Bottom-Up Parser
− Bottom-up parsing starts from the
bottom with the string and comes to the start symbol
using a parse tree.
Design of Top-Down Parser
•
For top-down parsing, a PDA has the following four types
of transitions −
•
Pop the non-terminal on the left hand side of the
production at the top of the stack and push its right-hand
side string.
•
If the top symbol of the stack matches with the input
symbol being read, pop it.
•
Push the start symbol ‘S’ into the stack.
•
If the input string is fully read and the stack is empty, go
to the final state ‘F’.
Design of Top-Down Parser
•
In top-down parsing, the algorithm marks the bottom of the
stack with a special $ symbol (which is not a symbol in
G
) and
puts
S
on the stack.
•
The stack is used to store (the unmatched portion) of a string
generated by the grammar that it matches with the input.
•
The top-down parser non-deterministically guesses which
rules to apply without even looking at the input. When the
top of the stack is an input symbol
a
, it must match with the
next symbol of the input.
•
When it is a variable
A
, the algorithm ignores the input and
replaces
A
with the RHS of some rule it is associated with.
•
The parser accepts if the input is fully matched when the stack
only has the bottom-of-stack symbol on it.
Design of a Bottom-Up Parser
•
For bottom-up parsing, a PDA has the following four types of
transitions −
•
Push the current input symbol into the stack.
•
Replace the right-hand side of a production at the top of the
stack with its left-hand side.
•
If the top of the stack element matches with the current input
symbol, pop it.
•
If the input string is fully read and only if the start symbol ‘S’
remains in the stack, pop it and go to the final state ‘F’.
Design of a Bottom-Up Parser
•
In bottom-up parsing, the algorithm marks the bottom of the
stack with $ and works from the input string
w
, pushing symbols
of
w
onto the stack and applying rules backwards (from right to
left) on the stack, eventually trying to produce a stack that only
has the start symbol
S
above the bottom- of-stack symbol.
•
Since pushing the symbols of
w
onto the stack one-by-one
means that when we pop them, they will come out in reverse
order.
•
Therefore, when we apply rules from right to left, we need to
begin with the reverse of the right-side.
•
Bottom-up parsing is also nondeterministic since the reverses of
more than one rule may be possible at a given step and one may
also choose to transfer an input symbol to the stack.
•
In practice, programming language grammars are designed so
that in bottom-up parsing, it is clear what to do next. Here it is in
PDA diagram form:
Example:
Consider the grammar that generates matched parentheses:
S
(
S
),
S
SS
,
S
ε
. We won’t draw the diagrams, but note that the reverse of (
S
) is )
S
( since the
individual symbols in the reverse are not flipped.
Pushdown Automata (PDA) is a powerful computational model that extends the capabilities of Finite Automata (FA) by incorporating a stack memory. PDAs can accept languages that FA cannot, making them essential in theoretical computer science. They consist of components like input tape, finite control, and stack, enabling them to process complex languages efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
UNIT IV PUSHDOWN AUTOMATA Ms. Shital Pawar Assistant Professor Computer Engineering Department Bharati Vidyapeeth s College of Engineering for Women, Pune
Pushdown Automata(PDA) 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. 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. 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.
Pushdown Automata(PDA) 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
Formal definition of PDA: The PDA can be defined as a collection of 7 components: Q: the finite set of states : the input set : a stack symbol which can be pushed and popped from the stack q0: the initial state Z: a start symbol which is in . F: a set of final states : mapping function which is used for moving from current state to next state.
Instantaneous Description (ID) ID is an informal notation of how a PDA computes an input string and make a decision that string is accepted or rejected. An instantaneous description is a triple (q, w, ) where: q describes the current state. w describes the remaining input. describes the stack contents, top at the left. Turnstile Notation: sign describes the turnstile notation and represents one move. * sign describes a sequence of moves. For example, (p, b, T) (q, w, ) In the above example, while taking a transition from state p to q, the input symbol 'b' is consumed, and the top of the stack 'T' is represented by a new string .
Example 1 Design a PDA for accepting a language {anb2n| n>=1}. Solution: Let us consider the string aabbbb for given language In this language, n number of a's should be followed by 2n number of b's. Hence, we will apply a very simple logic, and that is if we read single 'a', we will push two a's onto the stack. As soon as we read 'b' then for every single 'b' only one 'a' should get popped from the stack. a a a a a a a a Z0 a a Z0 a Z0 Z0 Z0 a Z0 Z0 Push a s Pop all a s
Reading all as and pushing as will be done at state q0 (q0, a, Z0) = (q0, aaZ0) Reading 1st a and pushing 2 a s onto the stack (q0, a, a) = (q0, aaa) Reading all remaining a s and pushing 2 a s for every a Now when we read b, we will change the state from q0 to q1 and start popping corresponding 'a'. Hence, (q0, b, a) = (q1, ) Reading 1st b and popping topmost a from stack Thus this process of popping 'b' will be repeated unless all the symbols are read. Note that popping action occurs in state q1 only. (q1, b, a) = (q1, ) Reading all remaining b sand popping one a for every b After reading all b's, all the corresponding a's should get popped. Hence when we read as input symbol then there should be nothing in the stack. (q1, , Z0) = (q2, ) popping Z0 from stack
Now we will simulate this PDA for the input string "aaabbbbbb". (q0, aaabbbbbb, Z0) (q0, aabbbbbb, aaZ0) (q0, abbbbbb, aaaaZ0) (q0, bbbbbb, aaaaaaZ0) (q1, bbbbb, aaaaaZ0) (q1, bbbb, aaaaZ0) (q1, bbb, aaaZ0) (q1, bb, aaZ0) (q1, b, aZ0) (q1, , Z0) (q2, ) ACCEPT
Example 2 Design a PDA for accepting a language {0n1m0n| m, n>=1}. Solution: In this PDA, n number of 0's are followed by any 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.
(q0, 0, Z0) = (q0, 0Z0) (Reading 1st0 s and pushing 0 s on stack) (q0, 0, 0) = (q0, 00) (Reading all 0 s and pushing all 0 s on stack) (q0, 1, 0) = (q1, 0) (Reading fist 1 and no operation on stack) (q1, 1, 0) = (q1, 0) (Reading all remaining 1 s and no operation on stack) (q1, 0, 0) = (q1, )(Reading last sequence of 0 s and popping all 0 s) (q1, , Z0) = (q2, Z0) (ACCEPT state) This scenario can be written in the ID form as: (q0, 0011100, Z0) (q0, 011100, 0Z0) (q0, 11100, 00Z0) (q0, 1100, 00Z0) (q1, 100, 00Z0) (q1, 00, 00Z0) (q1, 0, 0Z0) (q1, , Z0) (q2, Z0) ACCEPT Now we will simulate this PDA for the input string "0011100".
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, Z0) * (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, Z0, F) be a PDA. The language acceptable by empty stack can be defined as: N(PDA) = {w | (q0, w, Z0) * (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 3 Let L= {anbncmdm | n,m >=1} fin PDA to accept the language L Solution: Acceptance by empty stack Push sequence of a s onto the stack. For every b input symbol ,pop(erase) a from stack. Push sequence of c s onto the stack. For every d input symbol ,pop(erase) C from stack.
(q0, a, Z0) =(q0, aZ0) (push first a) (q0, a, a) =(q0, aa) (push all remaining a s) (q0, b, a) =(q1, ) (erase a for first b) (q1, b, a) =(q1, ) (erase all remaining a s for remaining b s) (q1, c, Z0) =(q2, cZ0) (push first c) (q2, c, c) =(q2, cc) (push all remaining c s) (q2, d, c) =(q3, ) (erase c for first d) (q3, d, c) =(q3, ) (erase all remaining c s for remaining d s) (q3, , Z0 ) =(q3, ) (acceptance by empty stack) Transition diagram for acceptance through empty stack PDA can be written as:
Example 3 Let L= {anbncmdm | n,m >=1} fin PDA to accept the language L Solution: Acceptance by final state Push sequence of a s onto the stack. For every b input symbol ,pop(erase) a from stack. Push sequence of c s onto the stack. For every d input symbol ,pop(erase) c from stack.
(q0, a, Z0) =(q0, aZ0) (push first a) (q0, a, a) =(q0, aa) (push all remaining a s) (q0, b, a) =(q1, ) (erase a for first b) (q1, b, a) =(q1, ) (erase all remaining a s for remaining b s) (q1, c, Z0) =(q2, cZ0) (push first c) (q2, c, c) =(q2, cc) (push all remaining c s) (q2, d, c) =(q3, ) (erase c for first d) (q3, d, c) =(q3, ) (erase all remaining c s for remaining d s) (q3, , Z0) = (q4,Z0 ) (Acceptance through final state) Transition diagram for acceptance through final state PDA can be written as:
Example 4 { L= aibjck | k>=0 and i+j =k} i) Find PDA accepting through final state ii) find PDA accepting through empty stack Solution: For every input symbol a , symbol x is pushed onto the stack. For every input symbol b , symbol x is pushed onto the stack. For every input symbol c , symbol x is popped from the stack.
2. PDA accepting through empty stack: (q0, a, Z0) =(q0, xZ0) (Reading first a and pushing one x on stack) (q0, a, x) =(q0,xx) (Reading all remaining a s and pushing x on stack) (q0, b, x) =(q1,xx) (Reading first b and pushing one x on stack) (q1, b, x) =(q1, xx) (Reading all remaining b s and pushing x on stack) (q1, c, x) =(q2, ) (Reading first c and popping x from stack) (q2,c, x) =(q2, ) (Reading remaining c s and popping x from stack) (q2, , Z0) =(q2, ) (acceptance through empty stack) Transition diagram
2. PDA accepting through final state: (q0, a, Z0) =(q0, xZ0) (Reading first a and pushing one x on stack) (q0, a, x) =(q0,xx) (Reading all remaining a s and pushing x on stack) (q0, b, x) =(q1,xx) (Reading first b and pushing one x on stack) (q1, b, x) =(q0, xx) (Reading all remaining b s and pushing x on stack) (q1, c, x) =(q2, ) (Reading first c and popping x from stack) (q2,c, x) =(q2, ) (Reading remaining c s and popping x from stack) (q2, , Z0) =(q3, Z0) (Acceptance through final state) Transition Diagram
Example 5 Design PDA for accepting a language L={WcWT | W {a,b}*} Solution: WT stands for reversal of string in w. For given language set of strings will be odd length palindrome. E.g. L = {aca, bcb, aacaa, abcba, bacab, abbcbba ..} Consider a string : abbcbba b b b b b b a Z0 Z0 a a a Z0 Z0 a a Z0 Z0 q1 q2 Z0 Z0 Z0 q0 q0 q1 q0 q1 q0 q1
Steps to design PDA for given language: 1. Read a sand push a it on stack without considering topmost stack symbol. 2. Read b sand push b it on stack without considering topmost stack symbol. 3. Read c without doing any stack operation. 4. Matching a swith pop operation (To match symbol a pop symbol a ) 5. Matching b swith pop operation (To match symbol b pop symbol b ) PDA for given language is: (q0, a, ) =(q0,a) (reading a and pushing a on stack) (q0, b, ) =(q0,b) (reading b and pushing b on stack) (q0, c, ) =(q1, ) (reading c without any stack operation) (q1, a, a) =(q1, ) (matching a with a and pooping a ) (q1,b, b) =(q1, ) (matching b with b and pooping a ) (q1, , Z0) =(q2, Z0) (acceptance through final state)
Example 6 Design PDA for accepting set of all strings over{a,b} with an equal number of a s and b s. The string should be accepted by 1. Final state 2. Empty stack Solution: Stack will store excess a s over b s or excess b s over a s. Consider input as: ababbaabba a b a b b a a b b a a a b a b Z0 Z0 Z0 Z0 Z0 Z0 Z0 Z0 Z0 Z0 Z0
There should be following possible cases: 1. Stack contains topmost symbol as Z0 and input is a (q0, a, Z0 ) =(q0, aZ0) (reading symbol a and pushing a on stack) 2. Stack contains topmost symbol as Z0 and input is b (q0, b, Z0 ) =(q0, bZ0) (reading symbol b and pushing b on stack) 3. Stack contains topmost symbol a and input is a (q0, a, a) =(q0, aa) (reading a and pushing a on stack) 4. Stack contains topmost symbol b and input is b (q0, b, b) =(q0,bb) (reading b and pushing b on stack) 5. Stack contains topmost symbol a and input is b (q0, b, a) =(q0, ) (reading b and popping a from stack) 6. Stack contains topmost symbol b and input is a (q0, a, b) =(q0, ) (reading b and popping a from stack)
PDA: For acceptance through empty stack (q0, a, Z0 ) =(q0, aZ0) (q0, b, Z0 ) =(q0, bZ0) (q0, a, a) =(q0, aa) (q0, b, b) =(q0, bb) (q0, b, a) =(q0, ) (q0, a, b) =(q0, ) (q0, , Z0) =(q0, ) PDA: For acceptance through final state (q0, a, Z0 ) =(q0, aZ0) (q0, b, Z0 ) =(q0, bZ0) (q0, a, a) =(q0, aa) (q0, b, b) =(q0, bb) (q0, b, a) =(q0, ) (q0, a, b) =(q0, ) (q0, , Z0 ) =(q1, Z0) Transition Diagram Transition Diagram
Types of PDA There are two types of Pushdown Automata: 1. DPDA( Deterministic PDA) 2. NPDA(Non- Deterministic PDA) DPDA NPDA DPDA are deterministic NPDA are non deterministic Every CFL can not be recognized by DPDA Every CFL can be recognized by NPDA There is only one move in every situation There could be multiple moves under a situation Palindrome can not be accepted by DPDA. Palindrome can not be accepted by NPDA. DPDA is less powerful NPDA is more powerful
Example 1 Design PDA to check whether a given string over{a,b} ends in abb Solution: String ending in abb forms a regular language and a regular language is accepted by DFA. PDA for regular language can be constructed in two steps: 1. Design DFA. 2. Convert the DFA into PDA by accepting no-stack operation to every transition in DFA.
So, for resulting PDA M=({q0,q1,q2,q3),{a, b},{z0}, , q0,z0,{q3}) (q0, b, Z0 ) =(q0, Z0) (q0, a, Z0 ) =(q1,Z0) (q1, a, Z0 ) =(q1,Z0) (q1, b, Z0 ) =(q2,Z0) (q2, a, Z0 ) =(q1,Z0) (q2, b, Z0 ) =(q3,Z0) (q3, a, Z0 ) =(q1,Z0) (q3, b, Z0 ) =(q0,Z0)
Example 2 Design PDA to check whether a given string over{a,b} having substring abb Solution: 1. Design DFA for given regular language 2. Convert DFA into PDA
So, for resulting PDA M=({q0,q1,q2,q3),{a, b},{z0}, , q0,z0,{q3}) (q0, b, Z0 ) =(q0, Z0) (q0, a, Z0 ) =(q1,Z0) (q1, a, Z0 ) =(q1,Z0) (q1, b, Z0 ) =(q2,Z0) (q2, a, Z0 ) =(q1,Z0) (q2, b, Z0 ) =(q3,Z0) (q3, a, Z0 ) =(q3,Z0) (q3, b, Z0 ) =(q3,Z0)
Example 3 Design PDA for detection of odd palindrome over{a,b} Solution: Odd length palindrome will be of form: WaWR and WbWR E.g: aba, bab, ababa, babab, bbabb, aabaa, As palindrome is odd length middle character is either a or b and first sequence of n characters will be equal to reverse of last sequence of n characters. Following are the steps to design PDA: There is no way to find middle character in a string. So middle character will be fixed non deterministically. 1. Push first sequence of n characters on stack where n is non deterministic. 2. Match last half sequence of n characters with characters on stack by using pop operation. 3. For middle character perform no operation on stack.
Note: perform stack operations irrespective of topmost stack symbol. 1. Push first half sequence of n characters on stack. (q0, a, ) =(q0 , a) (q0, b, ) =(q0 , b) 2. For middle character perform no operation on stack. (q0, a, ) = (q1 , ) (q0, b, ) = (q1 , ) 3. For last half sequence of n characters perform matching of by pop operation. (q1, a, a) =(q1 , ) (q1, b, b) =(q1 , ) 4. Acceptance through empty stack (q1, , Z0)= (q1 , )
So, PDA is: Acceptance through empty stack (q0, a, ) = {(q0, a), (q1, )} (q0, b, ) ={(q0, b) , (q1, )} (q1, a, a) = (q1 , ) (q0, b, b) = (q1 , ) (q1, , Z0)= (q1 , ) (acceptance through empty stack) Here, Q = (q0,q1) = {a, b} = {a,b,z0} Start state = q0 Initial stack symbol = Z0
Example 4 Design PDA for detection of even palindrome over{a,b} Solution: Odd length palindrome will be of form: WWR . E.g: aa, bb, abba, baab, bbbb, aaaa, As palindrome is even length first sequence of n characters will be equal to reverse of last sequence of n characters. Following are the steps to design PDA: There is no way to find middle position in a string. So middle character will be fixed non deterministically. 1. Push first sequence of n characters on stack where n is non deterministic. 2. Match last half sequence of n characters with characters on stack by using pop operation.
1. Push first half sequence on n characters on stack First symbol can be either a or b. (q0, a, Z0 ) = (q0 , aZ0 ) (Reading first symbol a and pushing a on stack) (q0, b, Z0 ) = (q0 , bZ0 ) (Reading first symbol b and pushing b on stack) Read first half sequence of n characters and push it on stack. (q0, a, a) = (q0 , aa) (q0, b, b) = (q0 , bb) (q0, b, a) = (q0 , ba) (q0, a, b) = (q0 , ab) 2. Read last half sequence of n characters and pop first half sequence from stack. For pop operation we will do state change. In last half sequence of n characters first symbol may be either a or b (q0, a, a) = (q1 , ) (Matching first a and popping a from stack) (q0, b, b) = (q1 , ) (Matching first b and popping b from stack)
Popping remaining a s and b s for matching last half sequence a s and b s. (q1, a, a) = (q1 , ) (Matching a and popping a from stack) (q1, b, b) = (q1 , ) (Matching b and popping b from stack) Acceptance through empty stack (q1, , Z0 ) = (q1 , ) So, PDA is: (q0, a, Z0 ) = (q0 , aZ0 ) (q0, b, Z0 ) = (q0 , bZ0 ) (q0, a, a) =[ (q0 , aa) , (q1 , ) ] (q0, b, b) = [(q0 , bb) , (q1 , ) ] (q0, b, a) = (q0 , ba) (q0, a, b) = (q0 , ab) (q1, a, a) = (q1 , ) (q1, b, b) = (q1 , ) (q1, , Z0 ) = (q1 , ) Here, Q = (q0,q1) = {a, b} = {a,b,z0} Start state = q0 Initial stack symbol =Z0
Example 5 Design PDA for detection of palindrome over {a,b} Solution: Palindrome can be of even length or odd length PDA for palindrome is: (q0, a, Z0 ) = { (q0 , aZ0 ) (q1 , Z0 ) } (q0, b, Z0 ) = (q0 , bZ0 ) (q1 , Z0 ) (q0, a, a) ={ (q0 , aa) , (q1 , ) , (q1 , a) } (q0, b, b) = {(q0 , bb) , (q1 , ) , (q1 , b)} (q0, b, a) = {(q0 , ba) . (q1 , a)} (q0, a, b) = (q0 , ab) , (q1 , a)} (q1, a, a) = (q1 , ) (q1, b, b) = (q1 , ) (q1, , Z0 ) = (q1 , ) (Acceptance through empty stack)
PDA and CFG The class of language accepted by pushdown automata is exactly the class of context-free-languages. Following three classes of language are same: Context Free Language defined by CFG. Language accepted by PDA by empty stack. Language accepted by PDA by final state. So, it is possible to find PDA for CFG. It is possible to find CFG for PDA 1. 2. 3. PDA by empty stack PDA by final state CFG Equivalence of PDA and CFG
CFG to PDA Conversion The following steps are used to obtain PDA from CFG is: Step 1: Convert the given productions of CFG into GNF. Step 1: The PDA will only have one state {q}. Step 2: The initial symbol of CFG will be the initial symbol in the PDA. Step 3: For non-terminal symbol, add the following rule: (q, , A) = (q, ) Where the production rule is A Step 4: For each terminal symbols, add the following rule: (q, a, a) = (q, ) for every terminal symbol
Example 1 Convert the following grammar to a PDA that accepts the same language. S 0S1 | A A 1A0 | S | Solution: The CFG can be first simplified by eliminating unit productions: S 0S1 | 1S0 | Now we will convert this CFG to GNF: S 0SX | 1SY | X 1 Y 0 The PDA can be: (q, , S) = {(q, 0SX) | (q, 1SY) | (q, )} (q, , X) = {(q, 1)} (q, , Y) = {(q, 0)} (q, 0, 0) = {(q, )} (q, 1, 1) = {(q, )} M =({q} , {0,1} , { S, X, Y, 0,1} , , q, S, )
Example 2 Construct PDA for the given CFG, and test whether 0104 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, )} (q, 010000, S) (q, 010000, 0BB) R1 (q, 10000, BB) (q, 10000,1SB) R2 (q, 0000, SB) R4 (q, 0000, 0BBB) R1 (q, 000, BBB) (q, 000, 0BB) R2 (q, 00, BB) R3 (q, 00, 0B) R2 (q, 0, B) R3 (q, 0, 0) R2 (q, ) ACCEPT Thus 0104is accepted by the PDA. Testing 0104i.e. 010000 against PDA: R3 R3 R3
Example 3 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), , q,S , } 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, )} Simulation: Consider the string aaabb (q, aaabb, S) (q, aaabb, aSb) R1 (q, aabb, Sb) (q, aabb, aSbb) (q, abb, Sbb) (q, abb, abb) (q, bb, bb) R2 (q, b, b) R3 (q, ) R3 ACCEPT R2 R1 R2 R1
Construction of CFG from PDA We can find CFG (G) for any PDA (M) such that, L(G) = L(M) We can construct an equivalent CFG for a PDA. For constructed CFG the variable will be of the form: x [p q] , where p, q Q and x . The PDA can be given by: M = { Q , , , , q0 , Z, } (Z is stack symbol) Then equivalent CFG is given by: G = (V, T, P, S) where, x V= {S, [p q] |p, q Q and X }
