MODEL PAPER

B.Tech (IT) Degree Examination

Second Year - Second Semester

DISCRETE MATHEMATICAL STRUCTURES II

Effective from the admitted batch of 2004-2005

Time: 3 hrs
Max Marks: 70

First Question is Compulsory

Answer any four from the remaining questions

All Questions carry equal marks

Answer all parts of any question at one place

1. Answer The following:
a) Give an example of a relation which is reflexive and transitive but not symmetric.
b) Find the value of A(2.2) where A(m, n) is defined below:
A(0,n)=n+1 if n > 0
A(m,0) = A(m-1, 1) if m > 0
A(m,n)=A(m-1,A(m,n-1) if m,n>0
c) How many binary operations are possible on a set having n elements?
d) What is a partially ordered set?
e) Find the hamming distance between the code words 10010101 and 10011001
f) If <G, *> is a group having 17 elements with the identity element e then list all subgroups of the group <G, *>.
g) Draw the Hasse diagram of the lattice (S, ≤) where S = {1,2,3.4,6,8,12,24} and for any elements a, b ∈ S, a ≤ b if and only if a divides b.

2. a) When do we say that a function is primitive recursive? Explain.

3. a) Show that the set of all the invertible elements of a monoid form a group under the same operations as that of the monoid.

b) State and prove the Lagranges theorem for groups.

4. a) Construct the decoding table for the group code
C={(0,0,0,0,0,0),(0,0,1,0,1,1),(0,1,0,1,0,1),(0,1,1,1,1,0),(1,0,0,1,1,1),(1,0,1,1,0,0),(1,1,0,0,1,0),(1,1,1,0,0,1)}

b) Prove that a code can correct all combinations of k or fewer errors if and only if the minimum distance between the any two code words is at least 2k+1.

5. a) What is the transitive closure of a relation? Find the transitive closure of the relation R = {(1,2),(2,3),(3,1),(1,3)} on the set S={1,2,3}.

b) Show that there are only five distinct Hasse diagrams for partially ordered sets that contain three elements.

6. a) Define the terms Grammar and Language and illustrate with examples.

b) Obtain a context free grammar which generates the language.
L = { w l w contains twice as many 0s and 1s }.

7. a) When do we say that (B, *, ⊕, ', 0, 1) is a Boolean Algebra? List all properties of a Boolean Algebra.

b) For the following Boolean expression give the circuit diagram representation and the Karnaugh map representation f = x'y'z + x'yz' + xyz'.

8. a) Explain the terms: Deterministic Finite state machine and Non-deterministic Finite state machine with examples.

b) Design a deterministic finite state acceptor for sentences in { a, b } such that every a has a b immediately to its right.