# VTU Previous Year Question Papers BE CS Fifth Semester

# Finite Automata and Formal Languages 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.