## Formal Languages and Automata Theory - May 2016

### VTU Computer Science (Semester 5)

Total marks: --

Total time: --
INSTRUCTIONS

(1) Assume appropriate data and state your reasons

(2) Marks are given to the right of every question

(3) Draw neat diagrams wherever necessary
**1(a)** Define the following with examples: i) Alphabet, ii) String.
4 marks

**1(b)** Define DFA. Write the DFA's for the following languages on ∑={a,b}.

i) The set all strings containing the substring 'ab'.

ii) L = {ω |ω| mod 3=0}
4 marks

**1(c)** Convert the following NFA to its equivalent DFA.

4 marks

**2(a)** Define a regular expression. Also write the regular expressions for the following languages.

i) The set of all strings ending in the substring '00' on ∑={0,1}

ii) L = {a^{n}b^{m} | n≥4, m≤3}.
4 marks

**2(b)** Prove that every language defined by a regular expression is also defined by a finite automation.
4 marks

**2(c)** Write the ∈-NFA for the regular expression ab(a+b)*.
4 marks

**3(a)** State and prove pumping lemma for regular languages.
4 marks

**3(b)** Show that the language L = {a^{n}b^{n} | n≥0} is not regular.
4 marks

**3(c)** Minimize the following DFA using table filling algorithm.

δ | 0 | 1 |

→q_{1} |
q_{2} |
q_{3} |

q_{2} |
q_{3} |
q_{5} |

*q_{3} |
q_{4} |
q_{3} |

q_{4} |
q_{3} |
q_{5} |

*q_{5} |
q_{2} |
q_{5} |

**4(a)** Define CFG. Design CFG's for the following languages:

i) L = {a^{n}b^{2n} | n≥0}

ii) L = {ω;ω^{R} / ω∈ {a,b}*}
4 marks

**4(b)** Write the LMD, RMD and parse tree for the string '+*-xyxy' using the grammar

E → EE | *EE | -EE | x | y
4 marks

**4(c)** What is an ambiguous grammar? Show that the following grammar is ambiguous:

E → E + E | E * E | (E) | id
4 marks

**5(a)** Define a PDA and explain the working of it with a neat diagram.
4 marks

**5(b)** Design a PDA for the language L = {ωω^{R} | ω ∈ {a, b}'. Draw the transition diagram and also write the sequence od ID's for the string 'abba'.
4 marks

**5(c)** Convert the following CFG to an equivalent PDA:

S → aA

A → aABC|bB|a

B → b

C → c
4 marks

**6(a)** Eliminate the useless symbols and productions from the following grammer.

S → AB|AC

A → aA|bAa|a

B → bbA|aB|AB

C → aCa|aD

D → aD|bC
4 marks

**6(b)** Define CNF and convert the following grammer into CNF.

S → Aba

A → aab

B → Ac
4 marks

**6(c)** Prove that the family of context-free languages is closed under union, concentration and star-closure.
4 marks

**7(a)** Define a turing machine and explain the working of a basic turing machine with a neat diagram.
4 marks

**7(b)** Design a turing machine for the language L = {a^{n}b^{n} | n≥1}. Write the transition diagram for the same and also, indicate the moves by the machine for the input 'aabb'.
4 marks

### Write short notes on

**8(a)**Multitape turing machine 4 marks

**8(b)** post's correspondence problem
4 marks

**8(c)** Applications of context-free languages.
4 marks

**8(d)** Chomsky hierarchy
4 marks