Automata Theory-Engineering-Mumbai University-Dec2019

MUMBAI UNIVERSITY

Subject: Automata Theory

Semester: 4

[Total Time: 3 Hours]
[Total Marks: 80 ]
N.B : 1) Question No.1 is compulsory.
2) Solve any three questions out of remaining five questions
3) Assumptions made should be clearly stated.

---

Q.1) Attempt any four sub-questions.

a) Construct the Finite Automata for binary number divisible by 2. [05M]

b) Design FA for decimal number divisible by 5. [05M]

c) Give formal definition of Turing Machine. [05M]

d) State and explain closure properties of regular languages. [05M]

e) Construct DFA accepting all the strings corresponding to the Regular expression. [05M]

1* 0 1 (0+11)^*

Q.2) a) Construct the following grammar to CNF. [10M]

S→ Ba | aB

A → bAA | aS | a

B → aBB | bS | b

b) Design Moore machine for binary adder. [10M]

Q.3) a) Design a DFA corresponding to the regular expression (a+b)^*aba (a+b)^* [10M]

b) Define CFA, obtain CGF for the following grammar.[10M]

(110+11)^*(10)*

Q.4) a) Define 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 [() (())]. [10M]

b) Construct a TM for 2′ s complement of a binary number. Simulate it for 1 0 1 0. [10M]

Q.5) a) Let G be the grammar. Find the leftmost derivation , rightmost derivation and parse tree for the string 001222. [10M]

G: S→ 0S| 1A | 2B| ε

A → 1A | 2B | ε

B → 2B | ε

b) Consider the CFG→aSb| bSa | SS| | ε, consider the string babbabaaaababb. Prove that given grammar is ambiguous by generating more than one parse tree for a given string. [10M]

 

Q.6) Write short notes on. [20M]

a) Applications of Automata Theory.

b) Chomsky Hierachy.

c) Power and limitations of PDA.

d) Halting Problem.