it

mg university

previous question paper

semester 4

cs

toc

theory of computation

s4

Previous question paper of 4th semester CS/IT MG University May 2014

**B.TECH DEGREE EXAMINATION,MAY 2014**

**Fourth Semester**

Branch : Computer Science and Engineering/Information Technology

CS 010 406/IT 010 404-THEORY OF COMPUTATION (CS,IT)

(New Scheme-2010 Admission onwards)

[Regular/Improvement/Supplementary]

Time : Three Hours Maximum:100 Marks

**Part A**

*Answer ***all ***questions.*

*Each question carries 3 marks.*

1. Define pigeonhole principle.

2. What are the applications of automata theory ?

3. Define a context free grammar.

4. What is the language accepted by TM ?

5. What does mean SAT.

(5*3=15 marks)

**Part B**

*Answer ***all ***questions.*

*Each question carries 5 marks.*

6. Write down the difference between primitive and partial recursive functions ?

7. Differentiate NFA and DFA.

8. What are the applications of pumping lemma ?

9. What are the special features of TM ?.

10.Write notes on Reduction problem ?

(5*5=25 marks)

**Part C**

*Answer ***all*** questions.*

*Each full question carries 12 marks.*

11. Define Diagonalization principle. Prove that the set is uncountable.

Or

12. Explain in detail about the Chomsky classification.

13. Conversion of DFA into regular expression.

Or

14.Write notes on deterministic and Non deterministic finite automation ?

15.State and prove the pumping lemma for CFL.

Or

16. Discuss about deterministic and Non deterministic PDA.

17. Explain the various techniques for Turing machine construction.

Or

18.Prove that the Halting problem is undecidable.

19. Write the characteristic features of p-completeness ? Explain with an example.

Or

20. State and prove Cooks theorem.

(5*12=60 marks)

theory-of-computation-4th-semester-mg-university-may-2014