Tamil Nadu Open University (TNOU) 2006 M.C.A .lP.G.D.C.ATHEORY OF COMPUTER SCIENCE - Question Paper

(

2049	MCA-10/
	PGDCA-08

M.C.A./P.G.D.C.A. EXAMINATION-JANUARY,

2006.

Second Semester

THEORY OF COMPUTER SCIENCE

Time : 3 hours    Maximum marks : 75

PART A (5 x 5 = 25 marks)

Answer any FIVE questions.

1.    Define equivalence relation. Give an example.

2.    For any two sets A and B, prove that

(a)    AC\BczA, AC\BqB

(b)    A_cSAnB=A

(c)    AflficAUS.

3.    Explain conjunctive normal form with an example.

4.    Prove that P -> (Q U R) <=> (P - Q) U (P fl).

5.    Construct the grammar for the Ranguage L{G) = \iⁿ b a^m/n,m> l},

6.    Define ambigous grammar. Give an example.

7.    Prove that, if a graph G has exactly two vertices of odd degree, there must be a path joining these two vertices.

PART B (5 x 10 = 50 marks)

Answer any FIVE questions.

8.    Define bijection. Show that the function f: R - R defined by fix)-3x -1, xe R is a bijection.

9.    Prove that the equivalence relation R defined on a set gives rise to partition of the set into equivalence classes.

10.    Obtain the product of sums canonical forms for

(a)    (P a Q a R) v (|P a R a Q) v

OaIQa ~\R).

(b)    (PaQ)v (|P a Q aR).

11.    Show that

(Vx) (P(x) v Q(x)) => (Vac) P(x) v (3x) Q(x).

12.    For the grammar G defined w > AB, B - a, A -> Aa, A6B, B-Sb, give derivation trees for the following sentential forms :

(a)    baSb    (b) baabaab

(c) bBABb.

13.    (a) Discuss the Konigsberg bridge problem.

(b)    Show that A given connected graph G is an Euler graph iff all vertices of G are of even degree.

14.    Explain the tree traversal methods with suitable algorithms.

3    2049

Attachment: tamil-nadu-open-university--tnou--2006-m-c-a--50164-1.pdf

Earning:   Approval pending.