LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

M.C.A. DEGREE EXAMINATION – COMPUTER APPLICATION
FIRST SEMESTER – November 2008
MT 1902 – MATHEMATICS FOR COMPUTER APPLICATIONS
Date : 111108 Dept. No. Max. : 100 Marks
Time : 1:00 – 4:00
Part A (Answer ALL questions) 2 x 10 = 20
 Define Lattice homomorphism between two lattices.
 With usual notations prove that (i)(ii) .
 Define context free grammar.
 What is the difference between deterministic finite automata and nondeterministic finite automata?
 Let G = (N, T, P, S), where N = {S}, T = {a}, P: {S → SS, S → a}. Check whether G is ambiguous or unambiguous.
 Give a deterministic finite automata accepting the set of all strings over {0, 1} containing 3 consecutive 0’s.
 If R and S be two relations defined by and , then find
RS, RR and R.
 Let and ,. Write the matrix of
of R and sketch its graph.
 Define ring with an example.
 State Kuratowski’s theorem.
Part B (Answer ALL questions) 5 x 8 = 40
 (a) Show that De Morgan’s laws given by and hold in a
complemented, distributive lattice.
(OR)
(b) Let be a lattice. For any prove the following distributive inequalities:
) and .
 (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.
(OR)
(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.
 (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)
(OR)
(b) Given an nondeterministic finite automaton which accepts L. Prove that there exists a deterministic finite automaton that accepts L.
 (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)
(OR)
(b) (i) Show that n^{3}+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)
 (a) Prove that there is a one toone correspondence between any two left cosets of H in G.
(OR)
(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)
 (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)
 (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)