Deterministic
Pushdown
Automata
(DPDA)
-SampathKumar S,
AP/CSE, SECE
2 21 November 2017
Types of PDA
The PDA can be classified into:
1. Deterministic PDA – PDA that has at most one
choice of move in any state.
2. Non-deterministic PDA - PDA that has more than
one choice of move in any state.
Sampath Kumar S, AP/CSE, SECE
3 21 November 2017
Problems to discuss:
111. Design a PDA which accepts L={anbn|n>1}
Solution:
Let q0 be the initial stat, q3 be the final state and z0
be bottom of the stack.
Read each ‘a’ and push into stack.
Then read each ‘b’ and pop out the stack for
matching a’s.
Where all b’s are read if the stack is empty then it is
successful
If any a’s are left over on the stack or b’s on input
tape, it is rejected.
Sampath Kumar S, AP/CSE, SECE
4 21 November 2017
Solution for sum 111:
The PDA moves are as follows:
δ(q0, a, z0) = (q1, az0) ….. (PUSH a)
δ(q1, a, a) = (q1, aa) ….. (PUSH a)
δ(q1, b, a) = (q2, ε) ….. (POP a)
δ(q2, b, a) = (q2, ε) ….. (POP a)
δ(q2, ε, z0) = (q3, z0) ….. (Accept and HALT)
Sampath Kumar S, AP/CSE, SECE
5 21 November 2017
Problems to discuss:
112. Design a PDA which accept the language
containing equal number of a’s and b’s over Σ={a,
b}.
113. Design a PDA which accepts L={anb2n|n>1}
114. Design a PDA which accepts L={a3bncn|n>0}
115. Design a PDA which accepts L={wcwr|w
(a+b)*}
116. Design a PDA which accepts the set of
balanced parenthesis. ([{()}])
Sampath Kumar S, AP/CSE, SECE
6 21 November 2017
Problems to discuss:
117. Design a PDA which accepts
L={apbncm|p+m=n}.
118. Design a PDA which accepts
L={0m1n0m|m,n>1}.
119. Design a PDA which accepts L={aibjck|i+j=k; i, j
>1}.
Sampath Kumar S, AP/CSE, SECE
7 21 November 2017
Problems to discuss:
120. Design a PDA which accepts
L={anbmcndm|n,m>1}.
121. Design a PDA which accepts L={anb2n+1|n>1}
Sampath Kumar S, AP/CSE, SECE
8 21 November 2017
Sampath Kumar S, AP/CSE, SECE
9 21 November 2017
நன்றி
Sampath Kumar S, AP/CSE, SECE
