Th Of Computation

567 B. E. VIth Semester Computer Science Engg. Examination THEORY OF COMPUTATION Paper-CSE-310-C Time allowed: 3 hours

Maximum Marks: lOa

Note: Attempt any five questions.

1.

(a) Give formal definition of finite automata which will accept all binary strings with even number of zero and ones. Also draw the transition diagram. 6 (b) Let L be a set accepted by non-deterministic finite automation. Then prove that there exists a deterministic finite automation that accepts L. Construct a DFA for following NFA. M

= ({qo' qj}, {O, I}, S,~, {qd) where

S (~, 0) = {~, qj}, S (qo' I) = {ql}, S (qJ' 0) = cp S(q"l)={CJo,q,). 2.

14

Why finite automater with output is needed? Write a procedure for converting a Mealy machine to Moore machine? Apply the procedure to the following Mealy machine. 20

567-~.()O().-P-2_Q_8 ('\i) P.T.O.

(2) 3.

State and explain the pumping lemma for regular sets. What are the applications of pumping lemma?

20

i

4.

State how a CFG can be converted to normal form. Convert the following grammar to GNF

G = {S

?

5.

AAIO A SSIl

-?

20

Give context free grammar for generating set of palindromes and then construct the PDA for this grammar. 20

6.

Explain the following : (i)

Universal Turing Machine. 10

(ii) Non deterministic Turing Machines.

10

7.

Show that the following problems about program in a real programming language are undecidable. (i)

Whether a given program can loop forever on some input

(ii) Whether the given program error produces an output (iii) Whether two programs produce same output on all inputs.

8.

Write short notes on : Relation between context sensitive language and recursive set. (ii) Linear bounded automata.

20 10,10

(i)

567<2.000

10 10