STUPIDSID
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 WWR
9 M
4(a)
Write short note on:
i) Recursively Enumerable Languages.
ii) Halting Problem of Turing Machine.
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