## Formal Languages and Automata Theory - Dec 2015

### Computer Science Engg. (Semester 5)

TOTAL MARKS: 100

TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.

(2) Attempt any **four** from the remaining questions.

(3) Assume data wherever required.

(4) Figures to the right indicate full marks.
**1 (a)** What is Automata? Discuss why study automata.(6 marks)
**1 (b)** Mention the difference between DFA, NFA and NFA → ∈.(4 marks)
**1 (c)** Design a DFA to accept the language L=(W/W is of even length and begins with 01).(6 marks)
**1 (d)** Design the NFA→∈ or NFA for the language given below:

i) abc, abd and aacd {Assume ∑=a, b, c, d}

ii) {ab, abc}* {Assume ∑=a, b, c}(4 marks)
**2 (a)** Convert the following NFA→∈ to DFA using ?Subset construction scheme?
(8 marks)
**2 (b)** Define Regular expression and write regular expression for the following languages:

i) L={a^{2n}b^{2m}: n≥0, m≥0}

ii) Language over {0, 1} having all strings not containing 00.(6 marks)
**2 (c)** Convert the regular expression (0+1)*1(0+1) to a NFA→∈.(6 marks)
**3 (a)** State and prove pumping Lemma theorem for regular language. Show that L={a^{n} b^{n}| n≥0} is not regular.(8 marks)
**3 (b)** What is Homomorphism? Explain with an example.(4 marks)
**3 (c)** Consider the transition table of DFA given below:

i) Draw the table of distinguishabilities of states.

ii) Construct the equivalent minimized DFA.

0 | 1 | |

→A | B | A |

B | A | C |

C | D | B |

*D | D | A |

E | D | F |

F | G | E |

G | F | G |

H | G | D |

(8 marks)
**4 (a)** Obtain a grammar to generate integers and write derivation for the unsigned integer 1965.(8 marks)
**4 (b)** Consider the grammar:

S→aS|aSbS|∈

Is the above grammar ambiguous? Show that the string aab has two-

i) Parse trees

ii) Left most derivations

iii) Rightmost derivations.(12 marks)
**5 (a)** Define PDA. Design PDA to accept the language L(M)={ωCω^{R}|ω∈(a+b)*} by a final state and also give the graphical representation of PDA.**(12 marks)
** 5 (b) Convert the following CFG to PDA: S→aABB|aAA A → aBB|a B→ bBB|A C→ a(8 marks)
6 (a) Consider the following grammar: S→ ASB|∈ A→ aAS|a B→ SbS|A|bb i) Are there any useless symbols? Eliminate if so. ii) Eliminate ∈ productions. iii) Eliminate unit productions. iv) Put the grammar into Chomsky Normal Form.(8 marks)
6 (b) Show that L={a^{n} b^{n} c^{n} | n≥0} is not context free.(4 marks)
6 (c) Prove that the context free languages are closed under union, concatenation and reversal.(8 marks)
7 (a) Design a turbine machine that performs the following function: q_{0}ω|- *q_{f} ωω for any ω ∈{1}* and also write its transition diagram.(12 marks)

**7 (b)**Explain the general structure of multitape and non deterministic Turing machines.(8 marks)

### Write short notes on:

**8 (a)** Applications of regular expressions.(5 marks)
**8 (b)** Applications of context free Grammars.(5 marks)
**8 (c)** Post's correspondence problem.(5 marks)
**8 (d)** Chomsky hierarchy.(5 marks)