BE CSE 611401 Mathematical Foundation for Computer Science Sathyabama University Nov 2010

Register Number

                               

SATHYABAMA UNIVERSITY

(Established under section 3 of UGC Act, 1956)

Course & Branch: B.E-CSE

Title of the Paper: Mathematical Foundation for Computer Science

Max. Marks: 80

Sub. Code: 611401                                                 Time: 3 Hours

Date: 22/11/2010                                                    Session: AN

______________________________________________________________________________________________________________________

PART - A                (10 X 2 = 20)

Answer ALL the Questions

1.     Given two sets A = {1, 3, 5, 7} and B (1, 2, 5, 8, 9}. Perform the union, intersection and difference operations on A and B.        

2.     Prove that for any sets A, B and C,

if AÇB = f and C Í B then A Ç C = f.

3.     Prove that formula (00*1)*1 = 1 + 0(0 + 10)*11

4.     State the Nonrecursive definition of d* for an NFA.

5.     What language is generated by the CFG with the each of the following production?

(a) S ® aSa½bSb½ Ù

(b) S ® aSa ½bSb½a½b

6.     State the definition of Deterministic PDA.

7.     Draw the transition diagram for a Turing Machine accepting the language {aⁿbⁿcⁿ |n ³ 0}

8.     Prove that: “if L is a recursively enumerable language whose complement is recursively enumerable, then L is recursive”.

9.     Show that the relation £ on a set of languages is reflective and transitive.

10.   Is the following decision problem unsolvable or solvable? Justify your answer WriteSymbol: Given TMT, and a symbol a in its tape alphabet, does T ever write a if it is started with a blank tape?

PART – B                       (5 x 12 = 60)

Answer All the Questions

11.   If L1, L2 and L3 be languages over some alphabet. In each part below two languages are given. Say what is the relationship (equal of one is subset of other) between them. Give reason for your answer with corresponding examples.

(a) L₁(L₂ÇL₃)          and  L₁L₂Ç L₁L₃

(b) L₁^*ÇL₂^*             and (L₁ÇL₂)

(c) L₁^*L₂^*                 and (L₁L₂)^*

(d) L₁^* (L₂ L₁^*)^*       and (L₁^* L₂)^* L₁^*

(or)

12.   (a) Prove that for any positive integers i, j and n, if i * j = n, then either                                             (4)

(b) Discuss the principles of Mathematical Induction.          (8) 

13.   Define Finite Automation. Draw the transition diagram for a FA to recognize L = {0, 1}^*{10}, the language of all string in {0, 1}^* ending in 00.

(or)

14.   Consider the NFA

Design the transition function table for the given NFA                (4)

Apply the subset construction to covert the given NFA to an FA

(8)

15.   Let G be the context free grammar with production

S ® S + S |S * S | (S) | a

and let G1 be the context-free grammar with productions

        S1 ® S1 + T | T

        T ® T * F | F

        F ® (S1) | a

Prove that L(G) = L(G1)

(or)

16.   Give the transition table for PDAs recognizing each of the following languages 

(a) The language of all nonpalindromes over {a, b}

(b) {aⁿx | n ³ 0, x Î {a, b}^* and |x| £ n}

(c) {aⁱb^jc^k | i,j,k ³ 0 and j = i  or j = k}

(d) {x Î {a, b, c}^*|n_a(x) < n_b(x) or n_a(x) < n_c(x)}

17.   (a) Consider the following regular languages

(i) L1 = {a, b}^*{a, b, a} {a, b}

(ii) L2 = {a, b}^*{a, b, c}

Draw the Finite Automation and construct Turing Machine for each.                                                                                 (8)

(b) Construct a Turing Machine that creates copy of its input string, to the left of the input with a symbol @ separating the copy from the original.                                                          (4)

(or)

18.   (a) Prove that: “If L is accepted by a nondeterministic Turing Machine T, and every possible sequence of moves of T causes it to halt, then L is recursive”

(b) Find unrestricted grammars to generate each of the following languages

(i) {aⁿbⁿaⁿbⁿ |n ³ 0}

(ii) {aⁿ x bⁿ | n ³ 0, x Î {a, b}^*, |x| = n}

(iii) {ss^rs |s Î {a, b}^*}

19.   (a) Give the proof for the lemma: “The language E = {e(T) | T is a TM} is recursive”                                                                (4)

(b) Discuss Halting problem to reduce one problem to another (8)

(or)

20.   (a) State the rice’s theorem and prove it.                               (8)

(b) Show that the problem of Subset can be reduced to the problem of Equivalent.                                                             (4)

Share This