Kerala University 2010-5th Sem B.Tech Computer Science Information Technology IT - Theory of computation (TOC) - Question Paper

Part A

Each question carries 4 marks.

I, Give the forma] definition ofNFA-.

2 Write regular expressions for the following,

(a) Set ul'all binnry slrings where the length of the string is an add number. <b) Se( of fill binaTy strings which end in 1 and do not contain 00.

3.    When is a CFG considered ambiguous? Give an example.

4.    List cite Chomsky hierarchy of languages.

5.    How (toes a mulli-tape Turing machine operate?

6.    State Myliill-Nerotle theorem.

7.    [tow- is a CKJ converted toGreibach Normal Form?

S. Show i|tai I.] = { w w^R is in L, L is regular } is regular.

9.    What is Church's Hypothesis?

10.    Wlial is a regular grammar?

Part B

Eiicli question tarries, 20 marks

] 1. (a) What are Moore and Mealy machines?

O) Design a Moure machine which outputs A' mod 4 where N ii a binary number

given as input,

OK

12 By applying dumping Lemma, show that I. * {aV i n>0) is not regular.

E 3. (a) Show that CFLs are not dosed under complementation. (10 marks)

(b| "Giivn a CFG in C'Nf or GhF, u given string (of the corresponding CFL) vf length n fan be* derived from the start symbol in exactly Ft steps".

Is ihe above statement true? Why?    (10 marks)

OR

14.    Given L = j a" h'*¹ a" m >0, rl > 0}. Using Pumping Lemma, prove that L is not a CFL.

15.    Show thal Halting Problem is undecirlabk-.

OR

16. Design a Turing Machine which accepts L = ( a" b" a* f ti > 0).

Attachment: kerala-university-2010-b-tech-computer-science-information-technology-39862-1.pdf

Earning:   Approval pending.