CS6503 Important Questions Theory of Computation
CS6503 Important Questions Theory of Computation Regulation 2013 Anna University free download. Theory of Computation TOC CS6503 Important Questions pdf free download.
Sample CS6503 Important Questions Theory of Computation:
PART – A
ANSWER ALL QUESTIONS (20 * 2 =40 MARKS)
1. What is Turing machine?
2. Give the difference between FA and TM.
3. Define Multitape Turing Machine. CS6503 Important Questions Theory of Computation
4. What is meant by halting problem?
5. What is Mapping reducibility?
6. Define Turing reducible. CS6503 Important Questions Theory of Computation
7. Give the definition of linear bound automaton.
8. Find a match in the following instance of PCP.
{[ab/abab],[b/a],[aba/b],[aa/a]}
9. What is Time complexity?
10. Define class P and NP completeness.
11. Prove that CLIQUE is in NP.
12. State the True or False for the following statement
(i) n^2=o(log^2 n)
(ii) nlogn=o(n^2) CS6503 Important Questions Theory of Computation
13. Define Probabilistic Turing machine.
14. Define trapdoor function.
15. What is one – way permutation?
16. Prove that CIRCUIT-VALUE is p-complete?
17. What are the classes L and NL? CS6503 Important Questions Theory of Computation
18. Define EXSPACE-complete.
19. Give the proof idea for FORMULA-GAME is PSPACE-complete.
20. Define PSPACE and PSPACE-complete?
PART – B Important question
ANSWER ANY FIVE QUESTIONS (5 X 12 = 60 MARKS )
21.(i) Give implementation-level description of Turing machines that decide the following language
over the alphabet{0,1}
(a) {w/w contains an equal number of 0s and 1s}. (8)
(ii) Show that a language is Turing-recognizable if and only if some enumerators enumerates it.(4)
22.(i) Prove that every CFL is decidable.(6)
(ii) Show that EQ(DFA) is a decidable language.(6)
23.(i) Prove that Recursive theorem.(6) CS6503 Important Questions Theory of Computation
(ii) Show that MIN(TM) is not Turing-recognizable.(6)
24.(i) Prove that HALT(TM) is decidable.(6)
(ii) Prove that EQ(TM) is neither Turing-recognizable nor Co-Turing-recognizable.(6) CS6503 Important Questions TOC Theory of Computation
25. Prove that HAMPATH is NP-complete.
| Subject Name | Theory of Computation |
| Subject code | CS6503 |
| Regulation | 2013 |
CS6503 Important Questions Theory of Computation click here to download
CS6503 Syllabus Theory of Computation
CS6503 Notes Theory of Computation
CS6503 Question Bank Theory of Computation