Loyola College M.Sc. Mathematics Nov 2008 Mathematics For Computer Applications Question Paper PDF Download


AB 31


FIRST SEMESTER – November 2008





Date : 11-11-08                 Dept. No.                                        Max. : 100 Marks

Time : 1:00 – 4:00


Part A (Answer ALL questions)                                                                              2 x 10 = 20

  1. Define Lattice homomorphism between two lattices.
  2. With usual notations prove that (i)(ii) .
  3. Define context free grammar.
  4. What is the difference between deterministic finite automata and non-deterministic finite automata?
  5. Let G = (N, T, P, S), where N = {S}, T = {a}, P: {S → SS, S → a}. Check whether G is ambiguous or unambiguous.
  6. Give a deterministic finite automata accepting the set of all strings over {0, 1} containing 3 consecutive 0’s.
  7. If R and S be two relations defined by and , then find

RS, RR and R.

  1. Let and ,. Write the matrix of

of R and sketch its graph.

  1. Define ring with an example.
  2. State Kuratowski’s theorem.

Part B (Answer ALL questions)                                                                              5 x 8 = 40

  1. (a) Show that De Morgan’s laws given by and  hold in a

complemented, distributive lattice.


(b) Let  be a lattice. For any  prove the following distributive inequalities:

) and .

  1. (a) Show that L(G) = is accepted by the grammar G = (N, T, P, S) where N = {S,A} T = {a, b}, P consists of the following productions: S → aSA, S → aZA, Z → bZB, Z → bB, BA → AB, AB → Ab, bB → bb, bA→ ba.


(b) Let the grammar G = ({S,A}, {a, b}, P, S) where P consists of S →aAS, S → a,               A → SbA , A → SS, A → ba. For the string aabbaa find a

(i) leftmost derivation

(ii) rightmost derivation

(iii) derivation tree.

  1. (a) (i) Define deterministic finite state automata.

(ii) Draw the state diagram for the deterministic finite state automata,                            M =   where Q =, Σ ={a, b}, F =  and δ is defined as follows:

    δ     a     b


Check whether the string bbabab is accepted by M.                                            (3+5)


(b) Given an non-deterministic finite automaton which accepts L. Prove that there exists a deterministic finite automaton that accepts L.

  1. (a) (i) Write short on Hasse diagram.

(ii) Let  and relation  be such that  if x divides y. Draw the

Hasse diagram of .                                                                                       (4+4)



(b) (i) Show that n3+2n is divisible by 3 using principle of mathematical induction.

(ii) If the permutations of the elements of {1,2,3,4,5} be given by

, then find

α -1-1.                                                                                        (4+4)



  1. (a) Prove that there is a one- to-one correspondence between any two left cosets of H in G.




(b) (i) If G is a graph in which the degree of every vertex is atlest two, then prove that G

contains a cycle.

(ii) Prove that the kernel of a homomorphism g from a group  to  is a subgroup

of  .                                                                                                                (4+4)



Part C (Answer ANY TWO questions)                                                                  2 x 20 = 40

16.(a)  Let G be (p,q)graph, then prove that the following statements are equivalent:

(i) G is a tree. (ii) Every two vertices of G are joined by a unique path (iii) G is connected

and  (iv) G is acyclic and p =  q+1.

(b) Let H be a subgroup of G. Then prove that any two left cosets of H in G are either

identical or have no element in common.                                                                  (14+6)


  1. (a) Let be a Boolean Algebra. Define the operations + and · on the elements of B by,


. Show that  is a boolean ring with identity 1.

(b) Prove that every chain is a distributive lattice.                                                           (15+5)

  1. (a) If G = (N, T, P, S) where N = {S, A,B}, T = {a,b}, and P consists of the following rules:

S → aB, S → bA, A → a, A → aS, A → bAA, B →b, B → bS, B → aBB. Then prove the following:

  • S w iff w consists of an equal number of a’s and b’s
  • A w iff w has one more a than it has b’s.
  • B w iff w has one more b than if has a’s


(b) State and prove pumping lemma.                                                                            (10+10) 


Go To Main page

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