Tamil University Model question paper - 2009 model question papers

Posted Date: 26 May 2010      Posted By:: Vijay Kumar Vishwakarma    Member Level: Gold  Points: 5 (₹ 1)

# 2009 Tamil University B.E Computer Science and Engineering Model question paper - 2009 Question paper

 Course: B.E Computer Science and Engineering University/board: Tamil University

SUBJECT : Theory of Computation SUBJECT CODE: CS1303
SEMESTER : 5th YEAR : III
TIME : 3Hrs Total Marks :100

PART A (10*2=20)
1. What is the difference between NFA and DFA?
2. Define e-closure of a State
3. For the grammar S?A1B,A?0A/?,B?0B/1B/?,give leftmost and right most derivation for the string 00101.
4. Construct CFG to generate {anbn /n?Z+}
5. Is it true that deterministic push down automata and non deterministic push down automata are equivalent in the sense of language of acceptances?
6. Define instantaneous description of a PDA
7. Define basic Turing machine.
8. Explain multitape Turing machine model
9. When a problem is said to be un decidable? Give an example of an undecidable problem.
10. Show that the union of recursive language is recursive.

PART-B-(5*16=80)
11. (a) (i) Prove that language L is accepted by some NFA if and only if L is accepted by some DFA . (8)
(ii) Consider the following ?-NFA .Compute the closure of each state and find its equivalent DFA.

? a B c
p {q} {p} ? ?
q {r} ? {q} ?
*r ? ? ? {r}

Or
(b) (i) P rove that a language L is accepted by some DFA iff L is accepted by some NFA.
(ii) Convert the following NFA to its equivalent DFA.

0 1
p {p,q} {p}
q {r} {r}
r {s} ?
*s {s} {s}

12. (a) (i) Construct an NFA equivalent to the following regular expression ((10)+(0+1))*01.
(ii) Check whether the language L={ 0n2/n?Z+ } is regular or not?
(Or)
(b) (i) Construct DFA equivalent to the NFA given below

0 1
?p {p,q} {p}
q {r} ?
*r ? ?

(ii) Prove that if L=L(A) for some DFA then there is a regular expression R such that L=L( R).
13. (a) (i) Prove that if L is a context-free language then there exists a PDA such that L=N(M).
(ii) Explain different types of acceptance of a PDA .Are they equivalent in sense of language acceptance? Justify your answer.
(or)
(b) If L is N(M) for some PDA M ,then prove that L is context free language

14. (a) (i) Design a TM to accept the language L= { anbn /n?Z+}

(ii) Explain with an example how finite control of a TM can be used to hold a finite amount of information.
(Or)
(b) (i) Explain how a TM can be viewed as a computing device on functions involving integers.
(ii)Design a TM to compute f(m,n)=m*n, for all m,n in Z+.
15. (a) Show that the language Lu is recursively enumerable but not recursive
(or)
(ii) Show that Ld is neither recursive nor recursively enumerable

### Related Question Papers:

• T.Y.B.Com Examination, March 2009 - Economics (Revised Course) University Question

• T.Y.B.Com Examination, March 2009 - Economics (OLD Course) University Questions

• T.Y.B.Com Examination, March 2009 - M.P.P University Question paper

• T.Y.B.Com Examination, March 2009 - Economics (OLD Course) University Question paper

• Title of the paper: PROGRAMMING IN C

• ### Categories

Submit Previous Years University Question Papers and make money from adsense revenue sharing program

Are you preparing for a university examination? Download model question papers and practise before you write the exam.

Looking for University or College admissions in India for 2021 - 2022 Academic Year?

Top Contributors
Today
Last 7 Daysmore... 