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

30views

written 8.1 years ago by

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 L_ww^r.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 L₁ and L₂ 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)

ADD COMMENT EDIT