# 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.**

**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.