**[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.

Login

Accessing this course requires a login. Please enter your credentials below!