Loyola College M.C.A. Computer Application April 2008 Mathematics For Computer Applications Question Paper PDF Download


XZ 30







Date : 05/05/2008            Dept. No.                                        Max. : 100 Marks

Time : 1:00 – 4:00


Answer ALL the questions.                                                                         (10 x 2 = 20)


  1. Define least upper bound of a poset.
  2. Define a Lattice.
  3. What are the logic operators?
  4. Construct a phrase structure grammar for the language .
  5. Define context-sensitive language.
  6. For a DFA ,

show that the string 011011 is in L(M)

  1. State the Pigeon hole principle.
  2. Draw the Hasse diagram for the divisors of 32.
  3. Define a bipartite graph with an example.
  4. Prove that every cyclic group is abelian.



Answer ALL the questions.                                                                         (5 x 8 = 40)


  1. (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.


(b) Discuss ‘negation’ and explain a method of constructing the truth table for P Ú ùQ and (P Ú Q) Ú ùP


  1. (a) Write a short note on principal conjunctive normal form and construct an equivalent formula             for ù.


(b) For a grammar  where P consists of the following production:

Then show that.


  1. (a) Let L be a set accepted by a non-deterministic finite automaton. Then prove that there exists a deterministic finite automaton that accepts L


(b) (i) Construct an equivalent deterministic automaton for a given non-deterministic automatonwhere .

(ii) If R and S are equivalence relations on the set X, prove that R Ç S is also an equivalence relation on X.


  1. (a) Prove that the equivalence relation ~ defined on the set A decomposes the set A into mutually disjoint equivalence classes.


(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.


  1. (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.


(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.



Answer any TWO questions.                                                                       (2 x 20 = 40)


  1. (a) Explain conditional and bi-conditional 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)


  1. (a) State and prove pumping lemma for regular sets.

(b) List any four applications of pumping lemma.

(c) Prove that if  and  be one-to-one onto functions, then  is also one-to-one onto and .

(10 + 4 + 6)


  1. (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:

View Full List ...

© Copyright Entrance India - Engineering and Medical Entrance Exams in India | Website Maintained by Firewall Firm - IT Monteur