Kerala University 2009 M.C.A Third Semester , 06.305.3 : THEORY OF COMPUTATION (Elective – I) - Question Paper

Illlllllllllllllll    (Pages : 2)    1888

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 Chomskys hierarchy ?

2.    State the pumping lemma for regular sets.

3.    Show that L ={a^m bⁿ c^m dⁿ/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.    (10x4=40 Marks)

iniHB

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.    (6x10=60 Marks)

Attachment: kerala-university-2009-m-c-a--40326-1.pdf

Earning:   Approval pending.