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