1
Automata Theory Question Paper - Dec 18 - Information Technology (Semester 4) - Mumbai University (MU)

## Automata Theory - Dec 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.

Q.1. Attempt any four sub-question.

1.a. State and explain advantages and limitation of regular and context free grammar.
(5 marks) 9082

1.b. Design a Mealy machine for a binary adder.
(5 marks) 9085

1.c. Give formal defination of PDA.
(5 marks) 6467

1.d. Construct the DFA that accept set of all strings over the alphabet $\sum = \{a, b\}$ containing either the substring 'aaa' or 'bbb'.
(5 marks) 9083

1.e. Find the CNF equivalent to

$S \rightarrow aAbB$

$A \rightarrow aA|a$

$B \rightarrow bB|b$

(5 marks) 9101

2.a. What is NFA? Design a NFA for a binary number where the first and last digit is same.
(10 marks) 9084

2.b. Write a necessary function for the given automata.

(10 marks) 9113

3.a.i. Find a regular expression RE corresponding to the following FA.

(05 marks) 9087

3.a.ii. Give a regular expression for a language over the alphabet $sum = \{a, b\}$ containing two a's.
(5 marks) 9089

3.b. Construct a Mealy machine that accepts strings ending in '00' and '11'. Convert the same to moore machine.
(10 marks) 9090

4.a. Design a PDA for CFL that checks the well formedness of parenthesis i.e the language L of all balanced string of two types of paranthesis "()" and "[]".

Trace the sequence of moves made corresponding to input string (([]){}).

(10 marks) 9108

4.b. Construct a TM accepting palindromes over $\sum = \{a, b\}.$
(10 marks) 9110

5.a. Let G be the grammar.Find the leftmost derivation,rightmost derivation and parse tree for string 001222.

$G: S \rightarrow 0S\ |1A|2B|\epsilon$

$A \rightarrow 1A\ |2B|\epsilon$

$B \rightarrow 2B |\epsilon$

(10 marks) 6464

5.b. Design a NFA for accepting input strings that contain either the keyword 000 or the keyword 010 and convert it into an equivalent DFA.

(10 marks) 9091

Q.6. Write a short notes on (Any four)

6.a. Variants of Turing Machines
(5 marks) 6471

6.b. Algorithm For CFG to CNF conversion.
(5 marks) 9483

6.c. Chomsky Hierarchy.
(5 marks) 9103

6.d. Limitation of Finite Automata
(5 marks) 9092

6.e. Halting problem.
(5 marks) 9111

1