Theory of Computation 4th Semester MG University May 2014

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