|
Download Model question papers & previous years question papers
The status of this post is Pending. The webmaster may be reviewing this post or have put on hold.
Reason: Please remove the page no. which you are referring. Type the questions only from those referred pages. |
|
Posted Date: 08 Nov 2010 Posted By:: aravind Member Level: Silver Points: 5 (Rs. 1)
|
2010 Anna University Chennai B.E Computer Science and Engineering Theory of computation important questions Question paper
TOC Important Questions
5th unit Theorems
1. Recursive language and recursive enumerable language
2. Decision problems and undecidable problems examples
3. Properties of recursive languages and recursive enumerable language
(4 theorems – 16 marks) (in boxes they will give )
4. Define diagonal language
5. Universal language – based theorems
6. Rice theorems
7. PN and NP problems
8. Samples for NP problems
9. NP – complete, NP – hard
Sample NP - complete and NP – hard problems
10. Binary equivalent of following integers is stored in a tape
Multiply the following by 2
(11 x 12 = 1100)
(100 x 10 = 1000)
11. Define diagonal language
12. Define the language LU and show that
LU is recursively enumerable but not recursive
13. Multiple track TM and multiple tape TM difference
14. Minimum no of stacks to represent a TM and for PDA
15. Count down M/C
16. Properties of CFL, properties of regular language
17. Final stack , empty stack – 2 theorems and proof of it
18. CFG – equivalent PDA - proof and theorems
19. PDA ? CFG ( theorem )
20. Pumping lemma – proof – 8 marks for CFL and regular language, problems( 4m / 2m )
2 mark questions
NOTE: (E^*=epsilon closure,E=epsilon)
1. Construct a CFG that generates all strings over E^* that are regular expression ( a, b, c, ),+,*,epsilon)
2. Write a CFG to generate a set of ( a^m, b^m,c^n )
3. Find the language generated by CFG
S ? OSO / 1 epsilon
S ? OSO / 1 S
4. Definition of push down automata
5. Diagonal language
6. Final language accepted by DFA given below
7. DFA and NFA ( DB )
8. Binary equivalent of integers
16 MARK QUESTIONS
1. I) PT a language is accepted by some ENFA
( iff ) if it is accepted by DFA
ii) Find the equivalent DFA for E^* NFA
2. I) Theorem for regular expression and equivalent finite automata
ii) Find regular expression equivalent to automata given using Arden's theorem
3. I) Construct minimum state automata equivalent to given automata whose transition table given
ii) Find regular expression corresponding to finite automata
4. Show that language is not regular
0^p ,p is prime
Find whether language is regular or not
L = W belongs to (a, b ) such that W = W^r
5. Construct a PDA accepted by empty stack in the language (a^m b^1 c^1)
6. Show that the grammar is ambiguous
7. State and prove pumping lemma for CFL
8. Design a TM for multiplication where x & y are stored as 0^x1 and o^y1
9. ST CFL are closed under union operation but not intersection
10. I) Find the grammar in CNF equivalent
ii) convert the grammar into GNF equivalent
11. Define universal language
Show that it is recursively enumerable but not enumerable
SOME OF THE IMPORTANT THEOREMS AND PROOFS
1. Proof by counter examples
2. Inductive proofs – problems
Extended del transition for NFA, DFA, sigma NFA
Language accepted by DFA < = > NFA
Refer Hopcroft book for below theorems
Pg : 77, theorem 2.11
Pg : 78, theorem 2.12
Theorem – 2.22, pg : 93
Theorem – 3.4, pg – 105
Pg – 116, theorem – 3.7
Pumping lemma for regular expression
Proof for pumping lemma
Applications for pumping lemma
Closure properties of regular expression page: 140
Theorems: 5.12, 5.14, 5.16
Page - 199 – theorem
Applications of CFG
PDA – definition, instantaneous description of PDA
Page: 245 - theorem - 6.9
Page: 248 - theorem – 6.11
1st unit – equivalent DFA and NFA, NFA with and without sigma transition
2nd unit – DFA to regular expressions and regular expressions to DFA , pumping lemma , properties of regular expression
3rd unit – refer above
Equivalent of CFG to PDA and PDA to CFG, deterministic properties of CFG
CNF and GNF - problem s and proofs
Return to question paper search
|
|
|
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.
|
|