Question Paper: Formal Languages and Automata Theory : Question Paper Jun 2012 - Computer Science Engg. (Semester 5) | Visveswaraya Technological University (VTU)

0

## Formal Languages and Automata Theory - Jun 2012

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

Power of alphabet

String

language(6 marks)
**1 (b)** Write DFR for ths following :

Set of all string not conatining (110)

Set of all string with exactly three consective O's(6 marks)
**1 (c) ** Convert the following NFA to DFA:

δ | 0 | 1 |

→q0 | q0 | q0,q1 |

q1 | q2 | q3 |

q2 | φ | φ |

(8 marks)

**2 (a)**For a given E-NFA computer the following :

Compute E-closure of each state.

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

Convert the automation to DFA

δ | ∈ | Q | b |

&tarr;p | {r} | {q} | {p,r} |

q | φ | {p} | φ |

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

(10 marks)

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

**2 (c)**Explain about text serch for address pattern(4 marks)

**3 (a)**If L and M are regular languages prove that L ? M is also regular(3 marks)

**3 (b)**Consider the homomorphism from the alphabet {0,1,2} to {a,b} defined by h(0)=ab,h(1)=b,h(2)=11

(i) What is h(2201)?

(ii) If is language 102

*what is h (L)?*

(iii) If L is the language (ab baa)bab what is h

(iii) If L is the language (ab baa)

^{-1}(L)(9 marks)

**3 (c)**Construct the product of DFA. (8 marks)

**4 (a)**Design CFG for the following :Set of all string of O's and whose number of O's equal to number of 1's (6 marks)

**4 (b)**Consider the grammer S→s b s/a .this grammer is ambiuos :Show that particular string aba ba ba has two

Parse trees

Left most derivation

Right most derivation.(10 marks)

**4 (c)**Write any one applictaion of CFG with example(4 marks)

**5 (a)**Design a PDA P to accept language L

_{ww}

^{r}.show that how PDA accept string 1111 with TD (10 marks)

**5 (b)**Prove that for a PDA P there exit CFG such that L(G)=N(P).(10 marks)

**6 (a)**consider the grammer s ?ASB/?

A ?aAS/a

B ?sbs/bb

i) Eliminate useless symbol

ii) Eliminate ?-production

iii)Eliminate until production

iv)Put the grammer into CNF.(10 marks)

**6 (b)**If L

_{1 }and L

_{2}are CFL ,then prove that family of context free languages are closed under union and concombination(10 marks)

**7 (a)**What is Turing machine and multi tape Turning machine ?show that languages accepted by these machines are same .(10 marks)

**7 (b)**Design turning mchine to accept the language consiisting of all polindromes of O's and 1's (10 marks)

### Write short notes on:

**8 (a)** Recursive language(5 marks)
**8 (b)** Post correspondance problem(5 marks)
**8 (c) ** universal machine (5 marks)
**8 (d)** Language that is not recrsively enumerbly.(5 marks)