ASSIGNMENT

Assignment A
Q1. a) What is a set? Explain various methods to represent a set in set theory.

Ans 1b): Define the following with the help of suitable examples.

Q2.   a)  What is a truth table? Discuss between Tautology and Contradiction? Prepare the truth tables for the following statements and then check which the tautologies are.
 
b) Let D be the set of all divisors of n. Construct a Hasse diagram for D16 D20   D30.

CASE STUDY 

Q1. Explain the Chomsky’s classification of grammar
Q2. State and Prove the Arden’s theorem for Regular Expression. Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.
Q 3. Construct a Context free Grammar, G generating all integers.

Assignment C
Q 1. If R is a relation on a set A to B then
Q 2.  If A and B are two sets with |A|=m and |B|=n then –

3. 

 
Q.4 If A={1,2,3} then the relation R={(1,1), (2.2)} is     
       
 
Q5. A function is called invertible if it  has
Q 6. If f(n)=n+1 and g(n)=2.n then fog is

Q 7.  If f(n)=n+1 and g(n)=2.n then gof is

Q 8. If A= (1, 2, 3, 4}. Which of the following ordered pairs is a function from A to A?
Q 9. The equivalent formula for P  Q is
Q 10. The solution of the recurrence ar = ar-1 + 3; n>= 2 with a1 = 2 is
 
Q 11. If |A|=n, then numbers of elements in the P{P{A}} is
Q 12.  If n(A)=100 and n(B)=200 and, then n(AυB)=
Q 13. The solution of the recurrence relation t = 3t -1 + 4t -2 with t0 = 0 and t1 = 5 is       
Q 14.  The pumping lemma for the regular set is based on

Q 15.  If ∑={a, b} then—
 
16. 
 
 

 
Q 17. The regular Expression describe by the grammar is--     
     
Q.18 A Relation is called a Partial order if it is-

 
Q.19  We say that f(n)=θ(g(n)) iff--     
 
Q.20 The Null (ε) transition is allowed in case of
Q 21. The grammar S -> aSb/Ab  AB -> BA  A -> bA/b B -> a is  of type
Q 22. Arden’s theorem is used to find
Q 23. A Finite Automata with some Auxiliary memory is Known as
Q 24. Let (Z, *) be an algebraic structure where Z is the set of integers and the operation * is defined by
  n* m = maximum (n, m), which of the following statements is true for (z,*)?.
Q 25.
 
Q 26.
 
Q 27. In case of Mealy machine, if the length of the input string |w|=n, then the output string will have
 
 
Q 28. In case of Moore machine, if the length of the input string |w|=n, then the output string will have
Q29.
 
Q 30. Type 2 grammar is also called      
Ans- b) Context-free
 
Q 31. If only Closure and associative properties is satisfied on any set for some binary operation, then
 the set is called     
Q 32. Turing Machine is an example of
Ans- b) CFG
 
Q 34. The number of edges in the Hasse diagram of (P{a,b,c}, C) is
Q 35
 
Q 36. A lattice is called a complemented lattice if

 
 
     
     
Q 37. The conjunctive normal form (CNF) of the function f(x,y) = x.y’ + x’y + x’y’ is
Q 38. The number of edges in the Hasse- diagram for the divisibility relation on the set
-- {3, 6, 12, 24, 48} is
Q 39. The equivalent formula for P  Q is
Q 40. Which of the regular expression corresponds to the grammar: S -> A B/AS, A -> a/Aa, B -> b?