Answer any one question from Q1 and Q2

1 (a)
Explain Basic Machines. What are its limitations? How Finite Automata more capable than Basic Machines? Justify with examples.

6 M

1 (b)
Write a CFG that generates language L denoted by, (a+b)*.bbb. (a+b)*.

4 M

2 (a)
Convert the following finite automation into its equivalent regular expression using Arden's Theorem.

6 M

2 (b)
If S={a,bb}, find the set of all strings in S* with string length less than or equal to 5. Also for given S, prove whether the following is true or false. (S*)

^{+}=(S^{+})*.
4 M

Answer any one question from Q3 and Q4

3 (a)
Design Moore Machine and Mealy Machine to find one's complement of a binary number.

6 M

3 (b)
Write the CFG for language L = {0 i 1 j 0 k | j > i +k}.
Show the derivation of the string '0111100'.

4 M

4 (a)
Define the following and give appropriate examples:

i) Unrestricted Grammar

ii) CFG

iii) Derivation Graph.

i) Unrestricted Grammar

ii) CFG

iii) Derivation Graph.

6 M

4 (b)
Construct FA for the regular expression: (11)*.010. (11)*.

4 M

Answer any one question from Q5 and Q6

5 (a)
Design a Turing Machine to recognize an arbitrary string divisible by 4, given ? = {0,1,2}.

10 M

5 (b)
Design a Turing Machine that accepts a language L = {0

^{n}1^{n}0^{n}| n > = 1}
8 M

6 (a)
Construct a TM that accepts a language L, a* ba *b.

6 M

6 (b)
How can Turing Machines be compared to computers?

6 M

6 (c)
Prove that the halting problem in Turing Machines is undecidable.

6 M

Answer any one question from Q7 and Q8

7 (a)
Construct transition table for PDA that accepts the language L = {a

^{2n}b^{n}| n > =1}. Trace your PDA for the input with n = 3.
10 M

7 (b)
Define push down automata (PDA). What are the different types of PDA? Give the applications of PDA.

6 M

8 (a)
Give a grammar for the language L(M), where:

\[ M=(\{q_0, q_1\}, \{0,1\}, \{z_0, x\}, \delta, q_0, z_0, \Phi). \\ And \ \delta \ is \ given \ by: \\ \delta (q_01, z_0) = (q_0\ xz_0) \ \ \ \ \delta (q_0, \varepsilon , z_0)= (q_0, \varepsilon) \\ \delta (q_01, x)= (q_0 \ xx) \ \ \ \ \ \delta (q_r1, x) = (q_1, \varepsilon) \\ \delta (q_00, x)= (q_r,x) \ \ \ \ \ \ \delta (q_00, z_0)=(q_0, z_0) \]

\[ M=(\{q_0, q_1\}, \{0,1\}, \{z_0, x\}, \delta, q_0, z_0, \Phi). \\ And \ \delta \ is \ given \ by: \\ \delta (q_01, z_0) = (q_0\ xz_0) \ \ \ \ \delta (q_0, \varepsilon , z_0)= (q_0, \varepsilon) \\ \delta (q_01, x)= (q_0 \ xx) \ \ \ \ \ \delta (q_r1, x) = (q_1, \varepsilon) \\ \delta (q_00, x)= (q_r,x) \ \ \ \ \ \ \delta (q_00, z_0)=(q_0, z_0) \]

8 M

8 (b)
Construct PDA for the following regular grammar:

S - > 0A |1B|0

A - > A0|B

B - > c|d

S - > 0A |1B|0

A - > A0|B

B - > c|d

8 M

Answer any one question from Q9 and Q10

9 (a)
Justify that the SAT Problem in NP complete.

8 M

9 (b)
Explain in detail, the polynomial time reduction approach for proving that a problem is NP Complete.

8 M

10 (a)
Explain the Node-Cover Problem with a suitable example.

8 M

10 (b)
Explain Tractable and In-tractable Problem.

4 M

10 (c)
Justify whether the Travelling Salesman Problem is a class P or class NP problem.

4 M

More question papers from Theory of Computation