Automata Theory Question Paper - May 18 - Information Technology (Semester 4)

64views

written 5.1 years ago by

Automata Theory - May 18

Information Technology (Semester 4)

Total marks: 80
Total time: 3 Hours INSTRUCTIONS
(1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Draw neat diagrams wherever necessary.

1.a. Design FA for decimal number divisible by 4.

(5 marks) 12343

1.b. Write a regular expression for $a^n \ b^m \ c^k$ where n+m is odd and k is even.

(5 marks) 9094

1.c. Design NFA for binary number divisible by 4 or 6.

(5 marks) 9095

1.d. Design Moore machine for binary adder.

(5 marks) 9096

2.a. Convert the following regular expression to NFA with Null moves, then convert it to DFA

$(0+1)^{*} 011(0+1)^*$

(10 marks) 9097

2.b. Give the Regular expression and corresponding DFA for all the words that begin and end with double letter.

(10 marks) 9098

3.a. Design the turing machine for $a^n \ b^n \ c^n$ where $n \geq 1.$

(10 marks) 6470

3.b. Write a Right linear grammar and left linear grammar for RE $(0+1)^*0$ and show derivation tree for 1010110.

(10 marks) 9104

4.a. Construct CFG for the following

(i) Alternate sequences of 0 and 1.

(ii) Don not contain 3 consecutive b's

(iii) $a^n \ b^m \ c^k$ where $k = n+m$

(10 marks) 9105

4.b. Design CFG for $a^n \ b^n$ where $n \geq1$ and convert it to Chomsky's Normal form.

(10 marks) 9106

5.a. What is Ambiguous Grammar,find the following grammar is ambiguous or not?

$S\rightarrow S+S$

$S\rightarrow S*S$

$S\rightarrow a$

$S\rightarrow b$

(10 marks) 9107

5.b. Design PDA for odd length palindrome, let $\sum = {(0, 1)}, L= \{W \ X \ W^R \ Where \ W \epsilon \sum^*\}$

(10 marks) 9109

6.a. Design Turing machine which adds 2 unary numbers and convert the Turing machine design to a program.

(12 marks) 9112

6.b. Explain the Applications of Automata (FM, PDA, TM) in detail with example.

(08 marks) 9114

ADD COMMENT EDIT