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