Theory Of Computation - May 2016

Computer Engineering (Semester 6)

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. 1 (a) Define One-to-one and Onto Functions. Also explain Compositions and Inverse of functions.(7 marks) 1 (b) Define NFA ' ?. Explain how to convert NFA ' ? into NFA and FA with suitable example.(7 marks) 2 (a) Define Mathematical Induction Principle and Prove that for every n≥1, $$ \sum^n_{i=1} i^2=n(n+1)(2n+1)/6.(7 marks)

Solve any one question from Q2(b) & Q2(c)

2 (b) Write Regular Expressions corresponding to each of the following subsets of {0,1}*
(i) The language of all strings in {0,1}* that containing at least two 0's.
(ii) The language of all strings containing both 101 and 010 as substrings.
(iii) The language of all strings that do not end with 01.(7 marks) 2 (c) Prove the formula (001)1 = 1+0(0+10)*11(7 marks)

Solve any two question from Q3(a), Q3(b) & Q3(c), Q3(d)

3 (a) Convert the Mealy machine shown in given figure into Moore machine.

Solve any two question from Q4(a), Q4(b) & Q4(c), Q4(d)

4 (a) Explain Pumping Lemma and its applications.(7 marks) 4 (b) Define Push Down Automata (PDA). Design and draw a deterministic PDA accepting strings with more a's than b's. Trace it for the string 'abbabaa'.(7 marks) 4 (c) Prove Kleene's Theorem Part 1 with illustration.(7 marks) 4 (d) Write PDA for following languages: {aⁱb^jc^k|i,j,k>=0 and j=1 or j=k}.(7 marks)

Solve any two question from Q5(a), Q5(b) & Q5(c), Q5(d)

5 (a) Draw the TM which recognize words of the form {aⁿbⁿcⁿ|n>=1}.(7 marks) 5 (b) Explain Universal Turing Machine and Church Turing Hypothesis.(7 marks) 5 (c) Design Turing Machine(TM) to accept Palindrome over {a,b}, even as well as odd.(7 marks) 5 (d) (i) Halting Problem(3 marks) 5 (d) (ii) Primitive Recursive Function.(4 marks)