Theory of Computation - Jun 2015

Computer Engg (Semester 5)

TOTAL MARKS: 100
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any four from the remaining questions.
(3) Assume data wherever required.
(4) Figures to the right indicate full marks.

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 marks) 1 (b) Write a CFG that generates language L denoted by, (a+b).bbb. (a+b).(4 marks) 10 (a) Explain the Node-Cover Problem with a suitable example.(8 marks) 10 (b) Explain Tractable and In-tractable Problem.(4 marks) 10 (c) Justify whether the Travelling Salesman Problem is a class P or class NP problem.(4 marks) 2 (a) Convert the following finite automation into its equivalent regular expression using Arden's Theorem. (6 marks) 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 marks)

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 marks) 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 marks) 4 (a) Define the following and give appropriate examples:
i) Unrestricted Grammar
ii) CFG
iii) Derivation Graph.(6 marks) 4 (b) Construct FA for the regular expression: (11).010. (11).(4 marks)

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 marks) 5 (b) Design a Turing Machine that accepts a language L = {0ⁿ 1ⁿ 0ⁿ | n > = 1}(8 marks) 6 (a) Construct a TM that accepts a language L, a* ba *b.(6 marks) 6 (b) How can Turing Machines be compared to computers?(6 marks) 6 (c) Prove that the halting problem in Turing Machines is undecidable.(6 marks)

Answer any one question from Q7 and Q8

7 (a) Construct transition table for PDA that accepts the language L = {a²ⁿ bⁿ | n > =1}. Trace your PDA for the input with n = 3.(10 marks) 7 (b) Define push down automata (PDA). What are the different types of PDA? Give the applications of PDA.(6 marks) 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) $$(8 marks) 8 (b) Construct PDA for the following regular grammar:
S - > 0A |1B|0
A - > A0|B
B - > c|d(8 marks)

Answer any one question from Q9 and Q10

9 (a) Justify that the SAT Problem in NP complete.(8 marks) 9 (b) Explain in detail, the polynomial time reduction approach for proving that a problem is NP Complete.(8 marks)