Question Paper: Formal Languages and Automata Theory : Question Paper Dec 2015 - Computer Science Engg. (Semester 5) | Visveswaraya Technological University (VTU)
0

## Formal Languages and Automata Theory - Dec 2015

### Computer Science Engg. (Semester 5)

TOTAL MARKS: 100
TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.
(2) Attempt any four from the remaining questions.
(3) Assume data wherever required.
(4) Figures to the right indicate full marks.
1 (a) What is Automata? Discuss why study automata.(6 marks) 1 (b) Mention the difference between DFA, NFA and NFA → ∈.(4 marks) 1 (c) Design a DFA to accept the language L=(W/W is of even length and begins with 01).(6 marks) 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 marks)
2 (a) Convert the following NFA→∈ to DFA using ?Subset construction scheme? (8 marks) 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 marks)
2 (c) Convert the regular expression (0+1)*1(0+1) to a NFA→∈.(6 marks) 3 (a) State and prove pumping Lemma theorem for regular language. Show that L={an bn| n≥0} is not regular.(8 marks) 3 (b) What is Homomorphism? Explain with an example.(4 marks) 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 marks) 4 (a) Obtain a grammar to generate integers and write derivation for the unsigned integer 1965.(8 marks) 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 marks)
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 marks) 5 (b) Convert the following CFG to PDA:
S→aABB|aAA
A → aBB|a
B→ bBB|A
C→ a
(8 marks)
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 marks)
6 (b) Show that L={an bn cn | n≥0} is not context free.(4 marks) 6 (c) Prove that the context free languages are closed under union, concatenation and reversal.(8 marks) 7 (a) Design a turbine machine that performs the following function:
q0ω|- *qf ωω for any ω ∈{1}
and also write its transition diagram.(12 marks) 7 (b) Explain the general structure of multitape and non deterministic Turing machines.(8 marks)

### Write short notes on:

8 (a) Applications of regular expressions.(5 marks) 8 (b) Applications of context free Grammars.(5 marks) 8 (c) Post's correspondence problem.(5 marks) 8 (d) Chomsky hierarchy.(5 marks)

 written 20 months ago by Team Ques10 ♦♦ 400