## 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^{n} 1^{n} 0^{n} | 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^{2n} b^{n} | 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)