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
