## Formal Languages and Automata Theory - Jun 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)** Define D.F.A. what are the different between D.F.A and N.F.A?(6 marks)
**1 (b)** Consruct a D.F.A to accept String over {a,b} such that every book of length five conatin atleast two a's(8 marks)
**1 (c) ** Define N.F.A and construct an N.F.A that accept the language 'aa*(a+b)**(6 marks)
** 2 (a) Define ?-NFA.Construct the &isin-NFA that accept 01(0+1)*.(6 marks)

**2 (b)**Let R be a regular expression.then there exists a finite automaton A=(Q,? &delta,q

_{0},F).(6 marks)

**2 (c)**

Convert the following ?-NFA to DFA

(8 marks)
**3 (a)** Sate and prove pumping lemma for the regular language.(7 marks)
**3 (b)** Obatin the R.E from The following FA using elimination method
(5 marks)
**3 (c) ** Minimize the following DFA using table filling algorithm

State | →A | B | (C) | D | E | F | G | H |

0 | B | G | A | C | H | C | G | G |

1 | F | C | C | G | F | G | E | C |

(8 marks)

**4 (a)**Consider the following grammer:

E?EE/E-E

E?EE/E/E

E?(E)

E?a/b/c

Obatin the left most derivation for the String (a+b

*c )*

Obatin the right most derivation for the String (a+b)c (8 marks)

Obatin the right most derivation for the String (a+b)

**4 (b)**Prove that the following grammer is ambiguous ,using the string "ibtibtaea".

S?iC

_{t}S/iC

_{t}SeS/a

C ?b(8 marks)

**4 (c)**Discuss the various application of contaxt free grammer(4 marks)

**5 (a)**Define PDA.Obtain a PDA to accept the following language:

L={n

^{a}(w)=nb(w)where n ?1}

Draw the transition diagram for PDA .Also ,show the moves made by aabbab.(12 marks)

**5 (b)**Obtain the PDA for the following grammer: S?aSa/aa

?bSb/bb(8 marks)

**6 (a)**What is an unit production? Begin with the grammar:

S→ABC|BaB

A→aA|BaC|aaa

B→bBb|a|D

D→ ε

Eliminate &epsilon- productions.

Eliminate any unit productions in the resulting grammar.

Eliminate any useless symbol in the resulting grammar.(10 marks)

**6 (b)**Obatin the following grammer in CNF:

S?OA/1B

A ?OAA/1S/1

B?!BB/OS/o(10 marks)

**7 (a)**Design a turing machine to accept the following language L={o

^{n}1

^{n}/n ?1}

Also show the sequence of moves made by the TM for the string "00001111"(14 marks)

**7 (b)**Write a note on multitape turing machine and non-Detreministic turing machine(6 marks)

### Write short notes on:

**8 (a)** Post correspondance problem(5 marks)
**8 (b)** Halting problem of TM(5 marks)
**8 (c) ** universal turing machine (5 marks)
**8 (d)** Application Of R.E(5 marks)