10
11

12

13

14

15
16
17

18

19

20

a)

b)
a)
b)
a)
b)

A7009
What do you mean by useless symbol in a grammar? Show the elimination of
useless symbols with an example.
Explain the different methods by which a PDA accepts a language.
Can we construct a Deterministic PDA for the language ww" ?Justify your
answer. Otherwise how can we modify this language to make it accepted by
DPDA.
PART D
Answer any two full questions, each carries 9 marks.
Define CFG for the following languages over the alphabets {a,b}
i. L={a™™b™c"n,m>0 }
11. L contains all odd length strings only
iii, L={0"1"2" ௩0)
Design a Push Down Automata for the language L= {a"b™ | n>0}
Trace your PDA with n=3.
Prove that the following languages are not regular

i. L = {0' such that i > 1} is not regular
11. L = [वा such that p isa prime 11 umber
PART E

Answer any four full questions, each carries 10 marks.
State and prove pumping lemma for Context Free Languages.
Construct a Turing machine that recognizes the language L = { a"b"c"| ‏محم‎ }
What is a Context sensitive grammar(CSG). Design a CSG to accept the
language 1, = (012 ௩0)
Define Linear Bound Automata
Write a note on Recursive Enumerable Languages
Discuss about Universal Turing Machines
Explain Chomsky’s Hierarchy of Languages
LetL = {x/ xe (३ + b+c)* and |x|, = |, = |x|c }. What class of language
does Lbelong? Why? What modification will you suggest in the grammar to
accept this language?
Discuss the Undecidable Problems About Turing Machines
೫ ೫ मं ‏د‎

Page 2 of 2

(3)

(3)
(3)

(9)

(9)

(9)

(10)
(10)
(6)

(4)
(5)
(5)
(6)
(4)

(10)