# 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 {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 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}*}, 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.

PART-B

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.