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

**1.b.**Design a Mealy machine for a binary adder.

**1.c.**Give formal defination of PDA.

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

**1.e.**Find the CNF equivalent to

$S \rightarrow aAbB$

$A \rightarrow aA|a$

$B \rightarrow bB|b$

**2.a.**What is NFA? Design a NFA for a binary number where the first and last digit is same.

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

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

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

**3.b.**Construct a Mealy machine that accepts strings ending in '00' and '11'. Convert the same to moore machine.

**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 (([]){}).

**4.b.**Construct a TM accepting palindromes over $\sum = \{a, b\}.$

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

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

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

**6.a.**Variants of Turing Machines

**6.b.**Algorithm For CFG to CNF conversion.

**6.c.**Chomsky Hierarchy.

**6.d.**Limitation of Finite Automata

**6.e.**Halting problem.