## Formal Languages and Automata Theory - Dec 2013

### 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)** Mention the difference between DFA,NFA and ?-NFA.(6 marks)
**1 (b)** Design a DFA which accept set of all string of 0's and 1's beginning with a 1 that,when interpreted as a binary integer ,is a multiple of 5.For example strings 101,1010 and 1111 are in the language :0,100,0101 and 111 are not (6 marks)
**1 (c) ** Convert the following NFA to DFA using construction method:

δ | 0 | 1 |

→p | {p,q} | {p} |

q | φ | {r} |

r | {p,r} | {q} |

(8 marks)

**2 (a)**Consider the following ?-NFA:

Compuer the ?-closure of each state .

Give the set of all string of lenghth 3 or less accepted by the automation

Convert the automation to DFA.

δ | ∈ | a | b |

→ | {r} | {q} | {p,r} |

q | φ | {p} | φ |

*r | {p,q} | {r} | {p} |

(8 marks)

**2 (b)**Give the regular expression for the following languages:

L={a

^{n}b

^{m}:n ?4,m ?2};

L={w:w?(0,1) and |w| mod 3=0}(4 marks)

**2 (c)**mention the application of regular expression (2 marks)

**2 (d)**prove that every language defined by RE is also defined by some finite automataion(6 marks)

**3 (a)**State and prove that pumping lemma of regular languages (6 marks)

**3 (b)**Obatin the regular expression or distinguish ?Minimize the following DFA using table finite automation using state climatation method (4 marks)

**3 (c)**When two sates are equivalent or distingushable ?minimize the following DFA using table filling algorithm

δ | 0 | 1 |

→q1 | q2 | q3 |

q2 | q3 | q5 |

q3 | q4 | q3 |

q4 | q3 | q5 |

*q5 | q2 | q5 |

(10 marks)

**4 (a)**Decline CFG .Design a context free grammer for the language :

L={a

^{i}b

^{j}c

^{k}, where i=J+k.j,k?0}

L={0

^{n+21n:n ?1}}(8 marks)

**4 (b)**What is an ambigous grammer? Show that grammer shown below is ambigous

S?AB|aaB

A&rarr|a

B ?b(6 marks)

**4 (c)**Consider the grammer

E?+EE/EE/-EE/x/y

Find the left most derivation ,right most derivation and parsetree for the string "+ * - xyxy.(6 marks)

**5 (a)**Discuss the language accepted by a PDA .design to PDA to accept the following language L=0<suo>2n 1

^{n}n?1}.draw the transmistion diagram for the constructed PDA ,Also show the moves made by PDA for the string "000011"</suo>(14 marks)

**5 (b)**Convert the following grammer to PDA that accept the same by empty stack: S?aABB/aAA

A?aBB/a

B?bBB/a

C ?a(6 marks)

**6 (a)**What are useless production ? Eliminate ? unit and unless production from following grammer

A?bA/Bba/aa

B ?aba/b/D ,

C ?CA/AC/B ,

D ?a /?(10 marks)

**6 (b)**Define chomskey normal form .convert the following CFG to CNF

S ?aSb/ab /Aa

A ? aab (6 marks)

**6 (c)**prove that the context free languages are closed under union(4 marks)

**7 (a)**Design a turing machine to accept the languages L={ww

^{R}:w?(a,b)*}.write its transition diagram .Also show the sequence of moves made by the TM for the string "aabbaa"(14 marks)

**7 (b)**Define turing machin .Explain with a diagram general structure of multiple turning machine(6 marks)

### Write short note on:

**8 (a)** Recursive language(5 marks)
**8 (b)** universal turing machine (5 marks)
**8 (c) ** Post correspondance problem(5 marks)
**8 (d)** Application Of Context free grammer(5 marks)