VTU CSE 5th Semester Finite Automata and Formal Languages Question Paper December 2010: You should practice more Question papers are the best materials to prepare for any exam. You can also overcome the exam fear and develop confidence. Exam papers will give you an idea about the real exam. By practicing more papers you will easily identify the important topics from every chapter. That will help you to score better marks. 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 Finite Automata and Formal Languages Question Paper December 2010.

## VTU CSE 5th Semester Finite Automata and Formal Languages Question Paper December 2010

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

Here you can check the Question Paper December 2010

**Note ; 1. Answer any FIVE full questions.**

** 2. Any missing data may be suitably assumed**

1 a. Define symbols, alphabets, strings and languages.

b. Define a DFA. Design a DFA to accept language with even number of a’s and odd number of b’s over £ = {a, b}, and process the string U – aaaabbb.

If D = (Qd, £, 5d, {qo}, F_{D}) is a DFA constructed by N = (Q_{N}, Z, 8n, qo, F_{N}) by the subset construction, then prove that L(D) = L(N).

2 a. Convert the following e – NFA to DFA.

b. Define regular expression. Write a regular expression to accept following languages.

i) Combination of a’s and b’s of even length. „ j j

ii) 2 symbol is ‘a’ and 3 symbol is ‘b’ from right end.

iii) L = {a^{n}b^{m} |where n > 3, b < 2}.

c. Convert the following regular expressions to its equivalent NFA.

(a + ab)* a b*.

3 a. Define and prove the pumping lemma for regular expression.

b.If L and M are regular languages, then so is L n M.

c. Convert the following DFA to a minimized DFA.

d. Explain the applications of regular expressions.

4 a. Define grammar. Write a grammar for the following languages.

i) L = {a^{n}b^{m} | m > n, n > 0}

ii) L={0″l^{2n}ln>0}

iii)L~{a^{n}b^{m}c |k = n + m}.

Consider the following grammar, write the LMD and RMD for the string U Check given grammar is ambiguous or not.

E * EE | – EE | + EE [ x | y.

List the applications of parser.

5 a. What are the different kinds of languages accepted by PDA? Design a PDA for language L = {a^{n}b^{ra}c^{n} | n > 0, m > 0}

and traverse the string w = aabcc.

b. Convert the given CFG to its equivalent PDA.

I—> a| b | la | lb 110 | II.

E -» 11 E * E j E + E | (E).

6 a. Remove the useless symbols from the given grammar :

aAa A -» ab [ bcC | DaA C -» abb | DD D aDA E -» aC.

b. Define CNF and GNF, Convert the following grammar into CNF.

E^E + T|T T -> T * F | F . F -> (E) 11 I —» a/b.

c. Prove that the following grammar is not regular L – {0^{n}l^{n}2^{n} | n> 1}.

7 a. Design a Turing machine to accept a language

L -{a^{n}b^{n} [ n > 1}.

Write transition diagram and table, process the string U ~ aaabbb.

b. Explain in detail,

i) Multitape turing machine

ii) Non – deterministic turing machine

iii) Restricted turing machine.

8 Write short notes on :

a. Variants of FA

b. DPDA

c. Turing machine and computers

d. Post’s correspondence problem.

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