Question Paper: Automata Theory Question Paper - May 18 - Information Technology (Semester 4) - Mumbai University (MU)

0

## 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.

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

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

**1.d.**Design Moore machine for binary adder.

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

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

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

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

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

**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$

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

**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$

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

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

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