advertisement

LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034 M.C.A. DEGREE EXAMINATION – COMPUTER APPLICATION FIRST SEMESTER – November 2008 AB 31 MT 1902 - MATHEMATICS FOR COMPUTER APPLICATIONS Date : 11-11-08 Time : 1:00 - 4:00 Dept. No. Max. : 100 Marks 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 R S, R R and R . 8. Let and of R and sketch its graph. 9. Define ring with an example. 10. State Kuratowski’s theorem. Part B (Answer ALL questions) , then find , 11. (a) Show that De Morgan’s laws given by complemented, distributive lattice. (b) Let and be a lattice. For any ) and . Write the matrix of 5 x 8 = 40 and hold in a (OR) prove the following distributive inequalities: . 12. (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. 13. (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 non-deterministic finite automaton which accepts L. Prove that there exists a deterministic finite automaton that accepts L. 14. (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) 1 (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 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 , , , , then find 2 3 1 4 5 1 2 3 5 4 5 4 3 1 2 3 2 1 5 4 α -1 -1 . (4+4) 15. (a) Prove that there is a one- to-one 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) 17. (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) 18. (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: (1) S w iff w consists of an equal number of a’s and b’s (2) A w iff w has one more a than it has b’s. (3) B w iff w has one more b than if has a’s (b) State and prove pumping lemma. (10+10) ************** 2