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)

(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. 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

machine ? Justify your answer.

5. Give two examples of NP-complete problem.

(5*3=15 marks)

**Part B**

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

*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**

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

*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