VTU Computer Science (Semester 5)
Formal Languages and Automata Theory
December 2015
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) What is Automata? Discuss why study automata.
6 M
1 (b) Mention the difference between DFA, NFA and NFA → ∈.
4 M
1 (c) Design a DFA to accept the language L=(W/W is of even length and begins with 01).
6 M
1 (d) Design the NFA→∈ or NFA for the language given below:
i) abc, abd and aacd {Assume ∑=a, b, c, d}
ii) {ab, abc}* {Assume ∑=a, b, c}
4 M

2 (a) Convert the following NFA→∈ to DFA using ?Subset construction scheme?

8 M
2 (b) Define Regular expression and write regular expression for the following languages:
i) L={a2nb2m: n≥0, m≥0}
ii) Language over {0, 1} having all strings not containing 00.
6 M
2 (c) Convert the regular expression (0+1)*1(0+1) to a NFA→∈.
6 M

3 (a) State and prove pumping Lemma theorem for regular language. Show that L={an bn| n≥0} is not regular.
8 M
3 (b) What is Homomorphism? Explain with an example.
4 M
3 (c) Consider the transition table of DFA given below:
i) Draw the table of distinguishabilities of states.
ii) Construct the equivalent minimized DFA.
  0 1
→A B A
B A C
C D B
*D D A
E D F
F G E
G F G
H G D
8 M

4 (a) Obtain a grammar to generate integers and write derivation for the unsigned integer 1965.
8 M
4 (b) Consider the grammar:
S→aS|aSbS|∈
Is the above grammar ambiguous? Show that the string aab has two-
i) Parse trees
ii) Left most derivations
iii) Rightmost derivations.
12 M

5 (a) Define PDA. Design PDA to accept the language L(M)={ωCωR|ω∈(a+b)*} by a final state and also give the graphical representation of PDA.
12 M
5 (b) Convert the following CFG to PDA:
S→aABB|aAA
A → aBB|a
B→ bBB|A
C→ a
8 M

6 (a) Consider the following grammar:
S→ ASB|∈
A→ aAS|a
B→ SbS|A|bb
i) Are there any useless symbols? Eliminate if so.
ii) Eliminate ∈ productions.
iii) Eliminate unit productions.
iv) Put the grammar into Chomsky Normal Form.
8 M
6 (b) Show that L={an bn cn | n≥0} is not context free.
4 M
6 (c) Prove that the context free languages are closed under union, concatenation and reversal.
8 M

7 (a) Design a turbine machine that performs the following function:
q0ω|- *qf ωω for any ω ∈{1}* and also write its transition diagram.
12 M
7 (b) Explain the general structure of multitape and non deterministic Turing machines.
8 M

Write short notes on:
8 (a) Applications of regular expressions.
5 M
8 (b) Applications of context free Grammars.
5 M
8 (c) Post's correspondence problem.
5 M
8 (d) Chomsky hierarchy.
5 M



More question papers from Formal Languages and Automata Theory
SPONSORED ADVERTISEMENTS