13

14

15

16

17

18

19

20

a)
b)

a)

b)

a)

b)

a)

b)

a)

b)

a)

b)

a)
b)

a)
b)
0)

00000CS301121901

Prove the equivalence of acceptance of a PDA by final state and empty stack.
Define a deterministic PDA. How a DPDA differs from a non-deterministic
PDA?
Let G be the grammar
ऽ > aB|bA, A -> alaS|bAA, B - b|bS|aBB
For the string aabbaabbba find
i) leftmost derivation, ii) parse tree, and iii) Is the grammar ambiguous?
Design ೩ PDA to accept the language L = {ww® | w € {0,1}*}.
PART E
Answer any four full questions, each carries10 marks.
Show that the language L = {ww|w ‏ع‎ {a, b}*} is nota CFL.
Design a TM to compute the 2’s complement of a binary string.
State and prove pumping lemma for context free languages. Mention the
application of pumping lemma.
Design a Turing machine to accept ,
L = {w ‏ع‎ {0,1}* | w has equal number of 0's and 1's}.
Compare context sensitive grammar and context free grammar. Can we design a
PDA for context sensitive languages? Justify your answer.
Design a TM to find the sum of two numbers m and n. Assume that initially the
tape contains ന number of 05 followed by ೫ followed by n number of 08
Are there any languages which are not recursively enumerable, but accepted by
a multi-tape Turing machine? Justify your answer.
Define formally Type 0, Type 1, Type 2 and Type 3 grammar. Show the
corresponding automata for each class
List the closure properties of Recursive Languages
Define a Universal Turing Machine (UTM). With the help of suitable arguments
show the simulation of other Turing machines by a UTM.
Compare recursive and recursively enumerable languages.
Show that the class of recursive languages is closed under complementation.
Show that the class of recursively enumerable languages are not closed under

complementation.

(6)
(3)

(4)

(5)

(5)

(5)

(6)

(4)

(5)

(5)

(5)

(5)

(4)
(6)

(3)
(3)
(4)