# Theory of Computation Fourth Semester MG University May 2013

### Exam Categories

btech computer science
mg university
it
s4
semester 4
cs
btech computer scence
toc
theory of computation

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

B.TECH DEGREE EXAMINATION,MAY 2013

Fourth Semester

Branch : Computer Science and Engineering/Information Technology

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

[Regular/Improvement/Supplementary]

Time : Three Hours Maximum:100 Marks

Part A

Each question carries 3 marks.

1. Explain pigeonhole principle.

2. State pumping lemma and its advantage.

3. Define the language recognized by the push down automata using empty stack.

4. Explain the multitape using machine mode .Is it more power than the basic turing

5. Give two examples of NP-complete problem.

(5*3=15 marks)

Part B

Each question carries 5 marks.

6. Discuss about Chomsky hierarchy of languages.

7. Design a DFA to accept odd number of as and even number of bs.

8. Construct a PDA for the language { an b 2n / n >= 0}

9. Describe the method of Godelization .

10.Let L be an NP-complete language. Then P = NP if and only if L . P .

(5*5=25 marks)

Part C

Each full question carries 12 marks.

11. (a) With an example explain computable and non computable functions.

Or

(b) Briefly explain Chomsky classification with an example.

12. (a) Design an NFA to recognize the regular expression (0+1) (0+1) * ( 0+1) using

Thompson construction algorithm and convert to an equivalent minimized DFA.

Trace for a string w=0001.

Or

(b) Briefly explain any three applications of finite automata in detail.

13. (a) ( i) Explain about Greibach Normal Form.

(ii) Is L = { a n b n c n / n >=1 } a context free language? Justify your answer.

Or

(b) For the grammar S-> aABC , A->aB/aB->bA/bC->a. Obtain the corresponding

PDA. Trace for the string w = aabaa.

14. (a) Construct a TM that finds the difference of two natural numbers.

Or

(b) Explain the post correspondence Problem with an example.

15. (a) Prove that subgraph isomorphism problem in NP-complete.

Or

(b) (i) How is Time complexity and space complexity defined in NP and P problems?

(ii) Is P=NP an undecidable problem.

(5*12=60 marks)

theory-of-computation-fourth-semester-mg-university-may-2013