Theory of Computation TE(2019) Computer Engineering
THEORY OF COMPUTATION
DEPARTMENT OF COMPUTER ENGINEERING
Subject : TOC ASSIGNMENT NO – 04 Unit : IV
THEORY QUESTION
1. Define PDA. What are different types of PDA? Applications of PDA?
2. Prove that "Let L be a language accepted by deterministic PDA, then the complement
of L, can also be accepted by, deterministic PDA
3. Proves the CFL are Closed under Union, Concatenation and Kleene’s closure.
4. Show that CFL are closed under intersection and Complementation.
5. Explain the working of top down parser and bottom up parser with example.
6. Differentiate between FA and PDA.
7. What are different ways to define PDA Acceptability
8. Explain acceptance by PDA
i ) By Final State
ii ) By Empty state
Construct PDA that accepts all palindrome string over {a, b} . Specify
simulation for string ‘aba’.
9. Explain Closure property of PDA with suitable example.
POSTDOWN AUTOMATA (PDA)
10. Construct PDA that accepts the language by the following CFG.SSS| (S) | ( )
11. Design a PDA for accepting a language L = {an bm cn | m,n>= l}
12. Design a PDA for accepting Language L = {W c WR | W ∈ (a,b)*}.
13. Construct PDA that accepts following language L anbn | n 0.Write simulation
for string ‘aaabbb’
n 2n
14. Design a PDA for the following LanguageL = {a b | n >=0}
15. Show that: L anbncn | n 1 not a CFL
2n n
16. Design a PDA for the following LanguageL = {a b | n >=1} n=3
SPPU University asked questions from 2015-2019
Theory of Computation TE(2019) Computer Engineering
POST MACHINE (PM)
17. What is Post Machine? Give formal definition of Post Machine. Construct a Post
Machine for accepting strings with equal number of a’s and b’s.
18. Construct post machine that accepts following language
L anbm | n 0,m 0
19. 13. Construct post Machine that accepts the following language.
L a b a | n 0
n n n
CFG TO PDA
20. Convert following CFG to PDA
S -> aSb | A
A -> bSa | S | Ɛ
21. Construct PDA for the following Regular Grammar :
S 0A | 1B | 0
A A0 | B
Bc|d
NPDA
22.
23.
24.
SPPU University asked questions from 2015-2019
Theory of Computation TE(2019) Computer Engineering
25. Construct the NPDA that accepts the language generated by
` S=S+S|S*S|4
PDA TO CFG
26.
Give Context Free Grammar (CFG) generating the language accepted
by the PDA M = {(q0, q1), (a ,b), , q0, Z0, q1} where δ is as follows.
1. (q0, a, Z0) (q0, XZ0)
2. (q0, a, X) (q0, XX)
3. (q0, b, X) (q1, ∈ )
4. (q1, b, X) (q1, ∈ )
5. (q1, ∈ , Z0) (q1, ∈ )
27.
28.
29.
SPPU University asked questions from 2015-2019
Theory of Computation TE(2019) Computer Engineering
MISCELLNEOUS EXAMPLES
30.
31.
*********************THE END********************
SPPU University asked questions from 2015-2019
