LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

M.C.A. DEGREE EXAMINATION – COMPUTER APPLICATION
FIRST SEMESTER – APRIL 2008
MT 1902 / CA 1804 – MATHEMATICS FOR COMPUTER APPLICATIONS
Date : 05/05/2008 Dept. No. Max. : 100 Marks
Time : 1:00 – 4:00
SECTION A
Answer ALL the questions. (10 x 2 = 20)
 Define least upper bound of a poset.
 Define a Lattice.
 What are the logic operators?
 Construct a phrase structure grammar for the language .
 Define contextsensitive language.
 For a DFA ,
show that the string 011011 is in L(M)
 State the Pigeon hole principle.
 Draw the Hasse diagram for the divisors of 32.
 Define a bipartite graph with an example.
 Prove that every cyclic group is abelian.
SECTION B
Answer ALL the questions. (5 x 8 = 40)
 (a) Prove that the complement of any element ‘a’ of a Boolean algebra is uniquely determined. Prove also that the map is an anti – automorphism of period 2 and satisfies (a Ú b)¢ = a¢ Ù b¢, (a Ù b)¢ = a¢ Ú b¢, a¢¢ = a.
(or)
(b) Discuss ‘negation’ and explain a method of constructing the truth table for P Ú ùQ and (P Ú Q) Ú ùP
 (a) Write a short note on principal conjunctive normal form and construct an equivalent formula for ù.
(or)
(b) For a grammar where P consists of the following production:
Then show that.
 (a) Let L be a set accepted by a nondeterministic finite automaton. Then prove that there exists a deterministic finite automaton that accepts L
(or)
(b) (i) Construct an equivalent deterministic automaton for a given nondeterministic automatonwhere .
(ii) If R and S are equivalence relations on the set X, prove that R Ç S is also an equivalence relation on X.
 (a) Prove that the equivalence relation ~ defined on the set A decomposes the set A into mutually disjoint equivalence classes.
(or)
(b) (i) A computer password consists of a letter of the alphabet followed by 3 or 4 digits. Find the total number of passwords that can be formed and the number of passwords in which no digit repeats.
(ii) Find the minimum number of students in a class to be sure that four out of them are born in the same month.
 (a) (i) Prove that a subgroup N of a group G is a normal subgroup of G iff the product of two left cosets of N in G is again a left coset N in G.
(ii) Define ring with an example.
(or)
(b) Prove that the following statements are equivalent for a connected graph G.
 G is Eulerian
 Every point of G has even degree
 The set of edges of G can be partitioned into cycles.
SECTION C
Answer any TWO questions. (2 x 20 = 40)
 (a) Explain conditional and biconditional connectives with an example.
(b) Define a Non – Deterministic Finite automata.
(c) For the non deterministic finite automaton,
give the transition table and show that 0100110 is in L (M).
(10 + 2 + 8)
 (a) State and prove pumping lemma for regular sets.
(b) List any four applications of pumping lemma.
(c) Prove that if and be onetoone onto functions, then is also onetoone onto and .
(10 + 4 + 6)
 (a) Show that in a graph G, any u – v walk contains a u – v path.
(b) Prove that a closed walk of odd length contains a cycle.
(c) State and prove Lagrange theorem. (4 + 4 + 12)
Latest Govt Job & Exam Updates: