Trending ▼   ResFinder  

KERALA UNIVERSITY MCA - II (SEM 3) MAY 2009 : Theory Of Computation

2 pages, 19 questions, 0 questions with responses, 0 total responses,    0    0
mca_india
   		+Fave Message
ProfileTimelineUploadsQ & A
 Home > mca_india >

Formatting page ...

*1888* 1888 (Pages : 2) Reg. No. : ..................................... Name : .......................................... Third Semester M.C.A. Degree Examination, May 2009 06.305.3 : THEORY OF COMPUTATION (Elective I) Time : 3 Hours Max. Marks : 100 PART A Answer all questions : 1. What is Chomsky s hierarchy ? 2. State the pumping lemma for regular sets. 3. Show that L ={am bn cm dn/m > 0, n > 0} is not a CFL. 4. Design a Moore machine which computes mod 4 for a binary input string treated as binary integer. 5. Explain the working of a two way finite automa. 6. What do you understand by ambiguous grammar ? 7. Define Greibach normal form. 8. Show that if a language L and its complement are both recursively enumerable then L is Recursive. 9. What is PDA ? 10. State Myhill-Nerode theorem. (10 4=40 Marks) P.T.O. 1 888 *1888* -2- PART B Answer any two questions from each Module. Module 1 11. Write a brief note on application of pumping lemma. 12. Describe the method to convert NFA to DFA with examples. 13. Distinguish between Mealy and Moore machines. Module 2 14. Find a deterministic finite state automation that accept the set consisting of all strings with exactly one a on {a, b} * 15. Write a brief note on normal forms of CFG with examples. 16. Write a note on Chomsky classification of languages. Module 3 17. Design a Turing machine to compute log2 n. 18. What are TMs ? Prove the equivalence of single tape and multi-tape TMs. 19. Show that the universal language is recursive. (6 10=60 Marks)

Formatting page ...

 

  Print intermediate debugging step

Show debugging info


 

Additional Info : Mca - II (sem 3) May 2009 Question Paper - Theory Of Computation
Tags : mca exam papers, mca question papers, ignou mca question papers, ptu mca question papers, mca sample question paper, mca mumbai university question papers, mca exam syllabus, mca exam question paper, online mca exam papers, online mca exam preparation, mumbai university mca question papers, ignou university mca question papers  


© 2010 - 2025 ResPaper. Terms of ServiceContact Us Advertise with us

 

mca_india chat