3
Automata Theory : Question Paper Dec 2014 - Information Technology (Semester 4) | Mumbai University (MU)

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)

3  upvotes

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.

Search

Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More