STUPIDSID
1 (a)
Define:
Power of alphabet
String
language
Power of alphabet
String
language
6 M
1 (b)
Write DFR for ths following :
Set of all string not conatining (110)
Set of all string with exactly three consective O's
Set of all string not conatining (110)
Set of all string with exactly three consective O's
6 M
1 (c)
Convert the following NFA to DFA:
| δ | 0 | 1 |
| →q0 | q0 | q0,q1 |
| q1 | q2 | q3 |
| *q2 | φ | φ |
8 M
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
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 M
2 (b)
prove that every language defined by RE is also defined by some finite automata
6 M
2 (c)
Explain about text serch for address pattern
4 M
3 (a)
If L and M are regular languages prove that L ? M is also regular
3 M
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 1*02 *what is h (L)?
(iii) If L is the language (ab baa)* bab what is h -1(L)
(i) What is h(2201)?
(ii) If is language 1*02 *what is h (L)?
(iii) If L is the language (ab baa)* bab what is h -1(L)
9 M
3 (c)
Construct the product of DFA.
8 M
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 M
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.
Parse trees
Left most derivation
Right most derivation.
10 M
4 (c)
Write any one applictaion of CFG with example
4 M
5 (a)
Design a PDA P to accept language Lwwr.show that how PDA accept string 1111 with TD
10 M
5 (b)
Prove that for a PDA P there exit CFG such that L(G)=N(P).
10 M
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.
A ?aAS/a
B ?sbs/bb
i) Eliminate useless symbol
ii) Eliminate ?-production
iii)Eliminate until production
iv)Put the grammer into CNF.
10 M
6 (b)
If L1 and L2 are CFL ,then prove that family of context free languages are closed under union and concombination
10 M
7 (a)
What is Turing machine and multi tape Turning machine ?show that languages accepted by these machines are same .
10 M
7 (b)
Design turning mchine to accept the language consiisting of all polindromes of O's and 1's
10 M
Write short notes on:
8 (a)
Recursive language
5 M
8 (b)
Post correspondance problem
5 M
8 (c)
universal machine
5 M
8 (d)
Language that is not recrsively enumerbly.
5 M
More question papers from Formal Languages and Automata Theory