STUPIDSID
Solve any one question.Q1(a,b,c) Q2(a,b,c)
1(a)
What is Kleen Closure? What is Positive Closure? For a given language L under what circumstances will L and L be equal?
6 M
1(b)
Construct a DFA over the alphabets{0,
1} for accepting the strings having number of 1's as multiple of 3.
1} for accepting the strings having number of 1's as multiple of 3.
6 M
1(c)
Check whether the given grammar is in CNF. If not then find its equivalent CNF.
S→bA| aB, A→bAA|aS|a, B→aBB|bS|b
S→bA| aB, A→bAA|aS|a, B→aBB|bS|b
8 M
2(a)
Define a Language of Polynomials recursively and give derivation for 7X2-3X3+15X
6 M
2(b)
Construct finite automata for the following regular expressions.
i) \[i)01[((10)^*+111)^*+0]^* 1\]
ii) \[1(1+10)^*+10(0+01)^*\]
i) \[i)01[((10)^*+111)^*+0]^* 1\]
ii) \[1(1+10)^*+10(0+01)^*\]
6 M
2(c)
Simplyfy the following grammar
i) S→Ab,
A→a,
B→C|b,
C→D,
D→E,
E→a
ii) S→0A0|1B1|BB,A→C,
B→S|A,
C→S|∈
i) S→Ab,
A→a,
B→C|b,
C→D,
D→E,
E→a
ii) S→0A0|1B1|BB,A→C,
B→S|A,
C→S|∈
8 M
Solve any one question.Q3(a,b) Q4(a,b)
3(a)
" If L1, &L2, are recursive languages, then L1∪L2, and L1∩L2 are also recursive " justify.
6 M
3(b)
What is NDTM? Construct a NDTM to recognize words of the form WW over alphabet {a,
b}.
b}.
12 M
4(a)
What is a post machine? Give formal definition of Post Machine. Construct a Post Machine for Having odd length and a as center element.
10 M
Write short note on (Any two) Q4(b) (i,ii,iii)
4(b)(i)
Universal Turing Machine(UTM).
4 M
4(b)(ii)
Languages accepted / decided by TM.
4 M
4(b)(iii)
Recursively Enumerable Languages.
4 M
Solve any one question.Q5(a,b) Q6(a,b)
5(a)
What is PDA? What are the different types of PDA? Give its applications.
7 M
5(b)
Obtain the CFG for the PDA given by M={{q0,
q1},
{0,
1},
{z0,
X}. δ,
q0, z0,
φ where is δ is given as
δ(q0,
1,
z0)={q0, xzo}
δ(q0, 1,
x)={q0,xx}
δ(q0,
0,
x)={q1,
x}
δ(q0,
ϵ,
z 0)={q0,
ϵ}
δ(q,
1,
x)={q1,
&varepsilon}
δ(q0,
z0)={q0,
z0}
q1},
{0,
1},
{z0,
X}. δ,
q0, z0,
φ where is δ is given as
δ(q0,
1,
z0)={q0, xzo}
δ(q0, 1,
x)={q0,xx}
δ(q0,
0,
x)={q1,
x}
δ(q0,
ϵ,
z 0)={q0,
ϵ}
δ(q,
1,
x)={q1,
&varepsilon}
δ(q0,
z0)={q0,
z0}
9 M
6(a)
Construct a PDA that accept L={anbn|n≥1} through Empty Stack.
6 M
6(b)
What is NPDA? Construct a NPDA for L={a b c| i≥j or j≥k}
10 M
Solve any one question.Q7(a,b) Q8(a,b,c)
7(a)
What do you mean by NP- Complete Problems? Listall the problem in this class and Explain any one with suitable example.
8 M
7(b)
Why do we need to reduce existing problems to NP-Complete problems? Explain with suitable example.
8 M
8(a)
What is SAT problem? Explain in detail.
8 M
8(b)
What are Tractable and Intractable problems? Explain.
4 M
8(c)
What is Computational Complexity? Explain.
4 M
More question papers from Theory of Computation