## Formal Languages and Automata Theory - Jun 2014

### 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)** Write the DFA for the following languages over ?{a,b}

The set of all strings ending with a&b

the set of all strings not containing the substring aab.

Set'of all strings with exactly three consecutive a'(10 marks)
**1 (b)** Define NFA"Convert the following NFA to its equivalent DFA [figure Q1.(b)]-
(10 marks)
**2 (a)** Consider the following ?NFA:

computer the ? -closure of each state

convert to DFA

∈ | a | b | c | |

→ | φ | {p} | {q} | {r} |

q | {p} | {q} | {r} | φ |

r | {q} | {r} | φ | {p} |

(8 marks)

**2 (b)**Define Regular expression. Convert the following automation to a regular expression using state elirnination technique. (10 marks)

**2 (c)**Convert the regular expression (0 + 1). | (0 +1) to anNFA(4 marks)

**3 (a)**State and prove pumping lemma for regular languages(10 marks)

**3 (b)**Define distinguishable and indistinguishable states.Minimize the following DFA using table filling algorithm

0 | 1 | |

A | B | F |

C | G | C |

C | A | C |

D | C | G |

E | H | F |

F | C | G |

G | G | E |

H | G | C |

3

(10 marks)**4 (a)**Define CFG. Write CFG for the following languages

L={0

^{n}|n ?1}

L={string /of a 's and b's with equal number grammer is ambigues(6 marks)

**4 (b)**What is an ambiguous grammar? Show that the following grammar is ambiguous.

E -+E+E E-E I E *E I E/E | (E) | a where whereE is the start symbol. Find the unambiguous grammar.(10 marks)

**4 (c)**Discu ss the applications of CFG(4 marks)

**5 (a)**Define PDA. Construct PDA that accepts the language L={ww

^{R}|w?(a+b+ and W

^{R}is the reversal of {w} .write ID's for the string aaabbbaa.(10 marks)

**5 (b)**Convert the following CFG to PDA and give the procedure for the same. S ?aABB|aAA

A?ABB|a

B ?bBB|A

C ??(10 marks)

**6 (a)**consider the following CFG

S ?aABB|aAA

A ?aBB|a

B ?bBB|A

C ? a

Shat are useless symbois?(ii) Eliminate e-productions unit productions and useless productions from the grammar.(10 marks)

**6 (b)**What is CNF and GNF? Obtain the following grammar in CNF S ?aBa|abba

A ? ab|AA

B ? aB|a(10 marks)

**7 (a)**Define'a turing machine and explain with neat diagram, the working of a basic turing machine(6 marks)

**7 (b)**Design a turing machine to accept the set of all palindromes over {a.b} *. iAlso, indicate the movesmade by turing machinefor the string ab(14 marks)

### Write short note on:

**8 (a)** Multipe turing machine(5 marks)
**8 (b)** Post's correspondence problem(5 marks)
**8 (c) ** Pumping lemma for CFL(5 marks)
**8 (d)** Recursive languages(5 marks)