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)
and 2 others joined a min ago.
teamques10
★ 69k
sagarkolekar
★ 11k