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 7X

^{2}-3X^{3}+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 L

_{1}, &L_{2}, are recursive languages, then L_{1}∪L_{2}, and L_{1}∩L_{2}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={{q

q

{0,

1},

{z

X}. δ,

q

φ where is δ is given as

δ(q

1,

z

δ(q

x)={q

δ(q

0,

x)={q

x}

δ(q

ϵ,

z

ϵ}

δ(q,

1,

x)={q

&varepsilon}

δ(q

z

z

_{0},q

_{1}},{0,

1},

{z

_{0},X}. δ,

q

_{0}, z_{0},φ where is δ is given as

δ(q

_{0},1,

z

_{0})={q_{0}, xz_{o}}δ(q

_{0}, 1,x)={q

_{0},xx}δ(q

_{0},0,

x)={q

_{1},x}

δ(q

_{0},ϵ,

z

_{0})={q_{0},ϵ}

δ(q,

1,

x)={q

_{1},&varepsilon}

δ(q

_{0},z

_{0})={q_{0},z

_{0}}
9 M

6(a)
Construct a PDA that accept L={a

^{n}b^{n}|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