MORE IN Theory of Computation
SPPU Computer Engineering (Semester 5)
Theory of Computation
December 2016
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

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.
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
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)^*$
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|∈
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}.
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}
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