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

## Formal Languages and Automata Theory - Jun 2012

### 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) Define:
Power of alphabet
String
language
(6 marks)
1 (b) Write DFR for ths following :
Set of all string not conatining (110)
Set of all string with exactly three consective O's
(6 marks)
1 (c) Convert the following NFA to DFA:

 δ 0 1 →q0 q0 q0,q1 q1 q2 q3 q2 φ φ

(8 marks) 2 (a) For a given E-NFA computer the following :
Compute E-closure of each state.
Give the set of all string of lenghth 3 or less accepted by the automation
Convert the automation to DFA
 δ ∈ Q b &tarr;p {r} {q} {p,r} q φ {p} φ *r {p,q} {r} {p}

(10 marks)
2 (b) prove that every language defined by RE is also defined by some finite automata(6 marks) 2 (c) Explain about text serch for address pattern(4 marks) 3 (a) If L and M are regular languages prove that L ? M is also regular(3 marks) 3 (b) Consider the homomorphism from the alphabet {0,1,2} to {a,b} defined by h(0)=ab,h(1)=b,h(2)=11
(i) What is h(2201)?
(ii) If is language 102 what is h (L)?
(iii) If L is the language (ab baa)
bab what is h -1(L)
(9 marks)
3 (c) Construct the product of DFA. (8 marks) 4 (a) Design CFG for the following :Set of all string of O's and whose number of O's equal to number of 1's (6 marks) 4 (b) Consider the grammer S→s b s/a .this grammer is ambiuos :Show that particular string aba ba ba has two
Parse trees
Left most derivation
Right most derivation.
(10 marks)
4 (c) Write any one applictaion of CFG with example(4 marks) 5 (a) Design a PDA P to accept language Lwwr.show that how PDA accept string 1111 with TD (10 marks) 5 (b) Prove that for a PDA P there exit CFG such that L(G)=N(P).(10 marks) 6 (a) consider the grammer s ?ASB/?
A ?aAS/a
B ?sbs/bb
i) Eliminate useless symbol
ii) Eliminate ?-production
iii)Eliminate until production
iv)Put the grammer into CNF.
(10 marks)
6 (b) If L1 and L2 are CFL ,then prove that family of context free languages are closed under union and concombination(10 marks) 7 (a) What is Turing machine and multi tape Turning machine ?show that languages accepted by these machines are same .(10 marks) 7 (b) Design turning mchine to accept the language consiisting of all polindromes of O's and 1's (10 marks)

### Write short notes on:

8 (a) Recursive language(5 marks) 8 (b) Post correspondance problem(5 marks) 8 (c) universal machine (5 marks) 8 (d) Language that is not recrsively enumerbly.(5 marks)