12

13

14

15

16

17

18

b)

a)
b)

a)

b)

a)
b)

a)
b)
a)
b)
a)
b)
a)

E1107 Pages: 3

Minimize the states of the, DFA given below

இ:
९.

PART C
Answer all questions, each carries 3 marks.

Give the CFG for the language ww® where w is string of zeroes and
ones.
What is a derivation tree? Give an example.
Compare DPDA and NPDA.
Explain any two closure properties of CFL.
PART D
Answer any two full questions, each carries 9 marks.
Prove that the language 170" is non-regular where n>0. (4.5)
Construct PDA for the language wew® where w is string of zeroes and (4.5)
ones.
Prove the equivalence of PDA accepting by empty stack and final (4.5)
states
Convert the grammar {S—ABaC|ABa, கக்கு B—>BaB]b, C>CC} (4.5)
to Chomsky normal form.
Convert 10 Greibach Normal form. {S—AB, துதிக்க 3-508/0] (4.5)
Prove the equivalence of CFG and PDA. (4.5)
PART E

Answer any four full questions, each carries 10 marks.

Prove that a"b"c" is non-context free language where 120.

What is a Universal Turing Machine? (5)
What is Pumping lemma for CFL? (5)
What is Halting problem? (5)
What is Linear Bounded Automata? (5)
What is Chomsky hierarchy? Give example for each type. (5)

Give the context sensitive grammar for the language a"b"c" where (5)

Page 2 of 3

(3)

(3)

(3)
(3)

(5)