SPPU Theory of Computation - May 2017 Exam Question Paper

SPPU Computer Engineering (Semester 5)
Theory of Computation
May 2017

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 from Q.1(a,b,c) &Q.2(a,b,c)

1(a) Prove or disprove the given regular expression

$\begin{align*} &i)\left ( r^*s^* \right )=\left ( r+s \right )^*\\ &ii)s\left ( rs+s \right )^*r=rr^*(rr^*s)^*r\end{align*}$

6 M

1(b) Define Pumping Lemma and apply it to prove the following

$L\left \{ 0^m1^n0^{m+n}|m>=1\ \text{and}\ \ n>=1\right \}$ /

6 M

1(c) What is the ambiguous grammar? Show that the grammar below is ambiguous, find the equivalent un ambiguous grammar.

$\begin{align*} &i)s\rightarrow ss|a|b\\ &ii)s\rightarrow ABA, A\rightarrow aAb \ |\ \epsilon ,B\rightarrow\ bB\end{align*}$

8 M

2(a) State Principle of Mathematical Induction and apply it to Show that

$1+4+7+....\left ( 3n-2 \right )=n\left ( 3n-1 \right )/2\ \text{for} \ n>0$

6 M

2(b) Construct of NFA that accepts the set of strings in(0+1)* such that some two 0's are Separated by string whose length is 4i, for some i>-0.

6 M

2(c) Find an equivalent left linear grammar for the given right linear grammar

$\begin{align*}& i)S\rightarrow bB|b, B\rightarrow bC|aB|b, C\rightarrow a\\ &ii)S\rightarrow 0A|1B, A\rightarrow 0C|1A|0,B\rightarrow 1B|1A|1, C\rightarrow 0|0A\end{align*}$

8 M

Solve any one question from Q.3(a,b) &Q.4(a,b)

3(a) What is Turing Machine? Give the formal definition of TM. Design a TM to compute multiplicationof two unary numbers.

9 M

3(b) What are the different ways for extension of TM? Explain. Construct a two tape TM to convert input W into WW^R

9 M

4(a) Write short note on:
i) Recursively Enumerable Languages.
ii) Halting Problem of Turing Machine.

8 M

4(b) What is a post machine? Give formal definition of Post machine. Construct a Post machine for Accepting strings having odd length and a or b as centre element.

10 M

Solve any one question from Q.5(a,b) &Q.6(a,b)

5(a) Construct a PDA that accepts the language generated by grammar.

$\begin{align*}& i) S\rightarrow 0S1|A,A\rightarrow 1A0|S|\varepsilon \\ &ii)S\rightarrow aABB|aAA,A\rightarrow aBB|a,B\rightarrow bAA|A\end{align*}$

8 M

5(b) Obtain the CFG equivalent to PDA given by the transition function.

$\begin{align*}&\delta \left ( q_{0},a,z_{0} \right )=\left \{ q_{0} az_{0}\right \}\ \delta \left ( q_{0} ,a,a\right )=\left \{ q_{0}aa \right \}\\ &\delta \left ( q_{0},b,a \right )=\left \{ q_{1} \varepsilon \right \}\ \ \ \ \delta \left ( q_{1}b,a \right )=\left \{ q_{1}\varepsilon \right \}\\ &\delta \left ( q_{q}\varepsilon ,z_{0} \right )=\left \{ q_{0} z_{0}\right \}\end{align*}$

8 M

6(a) What is a PDA? Construct a PDA that accept

$L= \left \{ a^{n}b^{n}|n\geq 1 \right \}$ / through Final State.

8 M

6(b) What is NPDA? Construct a NPDA for the set of all strings over {a, b} with odd length palindrome.

8 M

Solve any one question from Q.7(a,b) &Q.8(a,b)

7(a) What is Kruskal's ? How can we solve this problem using Turing Machine?

8 M

7(b) What do you mean by Polynomial Time Reduction? Explain with suitable example.

8 M

8(a) What do you mean by NP-Problems? Justify why the Travelling Sales man problem is a NP-Problem.

8 M

8(b) What is Clique Problem? Show that it is a NP-Complete problem.

8 M

More question papers from Theory of Computation

SPONSORED ADVERTISEMENTS