VTU Previous Year Question Papers BE CS Fifth Semester Formal Languages and Automata Theory June 2010

VTU Previous Year Question Papers BE CS Fifth Semester

Formal Languages and Automata Theory June 2010


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


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 {a11 bn | 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
* c A C
D c G
F c G


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

i) L ~ { w\/ | we {a, b}*}, wR 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.


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

L = { w | we {a, b}*, Na(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:

Qowh qfww for any we {1}


8 Write short notes on:

a. Multitape TM

b. Post correspondence problem

c. Chomsky hierarchy

d. Applications of regular expressions.

Leave a Comment