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

2views

written 8.7 years ago by

teamques10 ★ 68k

Automata Theory - Dec 2013

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) Define with example Moore and Mealy machine.(5 marks) 1(b) Find the equivalent DFA accepting the regular language defined by right linear grammar given as:
S$\rightarrow$aA|bB
A$\rightarrow$aA|bC|a
B$\rightarrow$aB|b
C$\rightarrow$bB(5 marks) 1(c) State and prove pumping lemma theorem for regular languages.(5 marks) 1(d) Differentiate between Deterministic PDA and Non-deterministic PDA.(5 marks) 2(a) Design a finite state machine to determine whether a ternary number base 3 is divisible by 5.[Hint:$\sum$={0,1,2}] (10 marks) 2(b) Design a Mealy machine for the languages (0+1)* (00+11)and convert it to a Moore machine.(10 marks) 3(a) Convert the following NFA with ε moves to DFA:
(10 marks) 3(b)

Let G be the grammar G={(S,X),{a,b},P,S}where production are
S$\rightarrow$aSX|b
X$\rightarrow$Xb|a
Find:
(i)Leftmost derivation (ii) Rightmost derivation and
Parse tree for the string "aababa".

(10 marks) 4(a) Design Turing machine for the language L={aⁿbn|n>=1} (10 marks) 4(b) Design a Turing machine to compare the binary numbers m and n such that if (m>n) output is G (m=n) output is E. (10 marks) 5(a) List and explain decision properties of regular language.
Explain the test for checking emptiness of a regular languages.(10 marks) 5(b) Construct left linear and right linear grammar for the regular expression:
(((01+10)11)00)(10 marks) 6(a) Construct a PDA equivalent to following grammar:
S$\rightarrow$OBB
B$\rightarrow$OS|1S|O
and show acceptance of 010⁴
by the PDA.(10 marks) 6(b) Reduce the following grammar to Greibach Normal form.
(i)S$\rightarrow$AB
A$\rightarrow$BSB|BB|b
B$\rightarrow$a
(ii)S$\rightarrow$01S|01
S$\rightarrow$10S|10
S$\rightarrow$00|^ (^ means Null (E)) (10 marks)

Any Four

7(a) Write short notes on(any four)
Post Correspondence problem(5 marks) 7(b) Chomsky Hierachy(5 marks) 7(c) Universal turing machine(5 marks) 7(d) Recursive and Recursively enumerable languages(5 marks) 7(e) Classes of complexity.(5 marks)

ADD COMMENT EDIT