A R5921 Pages: 2

9 Is the grammar {E—E+E]|E-Elid} ambiguous? Why? (3)
10 What is the difference between NPDA and DPDA? (3)
11 Is the language ww" where w is string of zeroes and ones, accepted by DPDA? (3)
3 Why?
PART D
Answer any two full questions, each carries 9 marks.

12 9) Show that L={0"/ p is a prime number} is not regular. (4.5)

0) Construct the CFG for the union of the languages 0117 and a"b" for n>0. (4.5)

13 a) Convert the grammar {S—AaCb|ABa, கக்கு, 3-२883|0, ಲಿಂ) to (4.5)

Chomsky normal form.

b) Construct the PDA for the language (0117) ', (4.5)
14 a) Give the formal definition of an NPDA. (3)
b) Show that NPDA and CFG are equivalent. (6)
PART E

Answer any four full questions, each carries 10 marks.
15 ൭) Consider L= {ww| we {0, 1}*}. Prove L is not a CFL. (5)
b) Explain Chomsky hierarchy and corresponding type0, typel, type2 and type 3 (5)
formalism.
16 a) Design a Turing machine that determines whether the binary input string is of (5)

odd parity or not

b) How does the Universal Turing machine simulate other Turing machines? (5)
17 a) Design ೩ Turing machine that accepts a"b™ where n>0 and m>n. (5)
b) Explain why Halting problem is unsolvable problem. (5)

18 a) What is the instantaneous description for a Turing machine? Explain with an (5)
example.
b) Show that normal single tape Turing machine can perform computations (5)

performed by multi-tape Turing machine (informal explanation is sufficient).

19 a) What isa recursive language? Give an example. (5)
b) How does a Turing machine differ from PDA and FSA? (5)
20 a) State pumping lemma for CFL. Mention one application of Pumping lemma (5)
b) What is a non-deterministic Turing machine? (5)

जे KKK

Page 2 of 2