Automata Theory : Question Paper Dec 2014 - Information Technology (Semester 4)

2views

written 8.1 years ago by

Automata Theory - Dec 2014

Information Technology (Semester 4)

TOTAL MARKS: 80
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Assume data if required.
(4) Figures to the right indicate full marks. 1(a) Explain Chomsky hierarchy.(10 marks) 1(b) Let G be the grammar.Find the leftmost derivation,rightmost derivation and parse tree for the string 001222
G:S$\rightarrow$0s|1A|2B| $\epsilon$
A$\rightarrow$1A|2B|$\epsilon$
B$\rightarrow$2B|$\epsilon$(10 marks) 2(a) Design a DFA that reject any string over (0,1,2)where 2 is immediately preceded by a 0.It should accept all other strings.(10 marks) 2(b) Design a DFA for the regular expression (a+b)aba(10 marks) 3(a) Design a mealy machine to accept all string ending with 00 or 11(10 marks) 3(b) Convert the following NFA to a reduce DFA (Final state is marked with)

δ	0	1
P	p q	p
q	r	r
r	s	-
s	s	s

(10 marks) 4(a)

Using pumping lemma prove that the following languages is not regular L=|ww|w $\epsilon${0,1}}

(10 marks) 4(b) Design Turing machine to generate the language given by a regular expression 00*(10 marks) 5(a) (i)Covert the following CFG to CNF
S$\rightarrow$aAbB
A$\rightarrow$aA|a
B$\rightarrow$bB|b
(ii)Construct a CFG over{a,b}to accept a set of all palindromes.(10 marks) 5(b) Design a PDA corresponding to the grammar S$\rightarrow$aSa|bSb|$\epsilon$ (10 marks)

any two

6(a) Write short notes on
variant of a Turning Machine(10 marks) 6(b) Post Correspondence problem(10 marks) 6(c) Halting Problem'(10 marks) 6(d) Pumping Lemma for Regular languages(10 marks)

ADD COMMENT EDIT