VTU CSE 5th Semester Formal Languages and Automata Theory Question Paper June 2010: To secure better marks in the exam, you should practice as many question papers as possible. It will give you information about the important chapters and concepts to be covered in all chapters.

Here we are providing you the complete guide on VTU CSE 5th Semester Formal Languages and Automata Theory Question Paper June 2010.

## VTU CSE 5th Semester Formal Languages and Automata Theory Question Paper June 2010

You must have Formal Languages and Automata Theory Question Paper along with the latest Computer Science 5th sem Syllabus to enhance your semester exam preparation.

Here you can check the Question Paper June 2010

**Note: Answer any FIVE full questions, selecting at least TWO questions from each part.**

**PART-A**

1 a.Define the following terms, with an example for each:

i) String ii) Alphabet iii) Powerset iv) Language.

b. Mention the differences between DFA, NFA and e-NFA.

c. Convert the following e-NFA to DFA. [Refer Fig.Ql(c)].

2 a. Define a regular expression: Find regular expression for the following languages on {a, b J: i)L= { a b : n>0, m>0 } ii) L = {-w : | w | mod 3 = 0 }, we {a, b}

b. Prove that if L andM are regular languages, then so is LnM .

c. Convert the regular expression (01 + 1) to an e-NFA.

3 a. State pumping lemma for regular languages. Prove that the language {a^{11} b^{n} | n > 1} is non-regular.

b. Define distinguishable and indistinguishable states. Minimize the following DFA using table filling algorithm.

f | 0 | 1 |

-> A | B | F |

B | G | C |

* c | A | C |

D | c | G |

E | H | F |

F | c | G |

G | G | E |

H | G | C |

4 a. Define CFG. Obtain CFG for the following languages;

i) L ~ { w\/ | we {a, b}*}, w^{R} is the reversal of w } ii) L = { w ; w has a substring ab}

b. What is an ambiguous grammar? Show that the following grammar is ambiguous. EE + E | E – E 1 E * E | E / E | (E) | a where E is the start symbol. Find the unambiguous grammar.

**PART-B**

5 a. Define PDA. Design PDA to accept the following language by final state.

L = { w | we {a, b}*, N_{a}(w) = Nb(w) }

Draw the graphical representation of PDA. Also, show the moves made by the PDA for the string abbaba.

b. Convert the following CFG to PDA.

S -> a ABB j aAA A-y aBB j a B ->bBB | A C a

6 a. What are useless symbols? Eliminate e, unit and useless productions from the following grammar:

S->AaA|CA|BaB A ->■ aaBa | CDA | aa | DC B->bB|bAB|bb|aS C Ca | bC [ D

D —> bD | €

b. What is CNF and GNF? Obtain the following grammar in CNF:

S —» aBa | abba A —y ab | AA

B —> aB | a

7 a. Prove that the context free languages are closed under union, concatenation and reversal.

b. Design a turning machine that performs the following function:

Qo^{w}h q_{f}ww for any we {1}

8 Write short notes on:

a. Multitape TM

b. Post correspondence problem

c. Chomsky hierarchy

d. Applications of regular expressions.

We have covered VTU CSE 5th Semester Formal Languages and Automata Theory Question Paper June 2010. Feel free to ask us any questions in the comment section below.