VTU Computer Science (Semester 5)
Formal Languages and Automata Theory
May 2016
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 M
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}
8 M
1(c) Convert the following NFA to its equivalent DFA.

8 M

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 = {anbm | n≥4, m≤3}.
8 M
2(b) Prove that every language defined by a regular expression is also defined by a finite automation.
8 M
2(c) Write the ∈-NFA for the regular expression ab(a+b)*.
4 M

3(a) State and prove pumping lemma for regular languages.
7 M
3(b) Show that the language L = {anbn | n≥0} is not regular.
6 M
3(c) Minimize the following DFA using table filling algorithm.
δ 0 1
→q1 q2 q3
q2 q3 q5
*q3 q4 q3
q4 q3 q5
*q5 q2 q5
7 M

4(a) Define CFG. Design CFG's for the following languages:
i) L = {anb2n | n≥0}
ii) L = {ω;ωR / ω∈ {a,b}*}
8 M
4(b) Write the LMD, RMD and parse tree for the string '+*-xyxy' using the grammar
E → EE | *EE | -EE | x | y
6 M
4(c) What is an ambiguous grammar? Show that the following grammar is ambiguous:
E → E + E | E * E | (E) | id
6 M

5(a) Define a PDA and explain the working of it with a neat diagram.
5 M
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'.
10 M
5(c) Convert the following CFG to an equivalent PDA:
S → aA
A → aABC|bB|a
B → b
C → c
5 M

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
7 M
6(b) Define CNF and convert the following grammer into CNF.
S → Aba
A → aab
B → Ac
6 M
6(c) Prove that the family of context-free languages is closed under union, concentration and star-closure.
7 M

7(a) Define a turing machine and explain the working of a basic turing machine with a neat diagram.
8 M
7(b) Design a turing machine for the language L = {anbn | n≥1}. Write the transition diagram for the same and also, indicate the moves by the machine for the input 'aabb'.
12 M

Write short notes on
8(a) Multitape turing machine
5 M
8(b) post's correspondence problem
5 M
8(c) Applications of context-free languages.
5 M
8(d) Chomsky hierarchy
5 M



More question papers from Formal Languages and Automata Theory
SPONSORED ADVERTISEMENTS