MCA /1st SEM/MCAP 1104/2017

Group - E MCA /1st SEM/MCAP 1104/2017

DISCRETE MATHEMATICS
8. (a) Briefly discuss with example type-0, type-1, type-2 and type-3
grammars.
(MCAP 1104)

(b) From the state transition table of the following NFA obtain it’s Time Allotted: 3 hrs Full Marks: 70
equivalent DFA. Figures out of the right margin indicate full marks.
NS
Σ Candidates are required to answer Group A and
PS a=0 a=1 Any 5 (five) from Group B to E, taking at least one from each group.
S0 {S0,S1} {S1} Candidates are required to give answer in their own words as far as
practicable.
S1 {S2} {S2}
Group – A
(Multiple Choice Type Questions)
S2  {S2}
1. Choose the correct alternative for the following: 10 × 1=10
(1.5 × 4) + 6 = 12
(i) If the general term of the sequence { ak } = ak ,then the corresponding
9. (a) Define Mealy machine and Moore machine. Construct a Moore generating function is
machine from the following Mealy machine : (a) 1/(1 - ax) (b) 1/(1 - x) (c) k/(1 - x) (d) a/(1 - x).
(ii) If n be the number of vertices, e be the number of edges and k be the
Present Next State number of components then
State a=0 a=1
(a) e > n+k (b) e ≥ n-k (c) e ≤ n-k (d) none of these.
State Output State Output
S0 S0 1 S1 0 (iii) If the function f : RR is defined by f(x)= 3x - 4, when x > 0
S1 S3 1 S3 1 = - 3x + 2, when x ≤ 0
S2 S1 1 S2 1 then f-1(2) =
S3 S2 0 S0 1 (a) {2} (b) {0, 2} (c) {-2, 2} (d) none of these.
(iv) The cardinality of a power set of a non-empty set A is
(b) Show that the language {0 10 : 𝑛 ≥ 1} is not a regular language. (a) 2|A| (b) 2|A| (c) |A|2 (d) |A|2 - |A|.
4 + 5 + 3 = 12
(v) In how many ways can a president and vice president be chosen from
a set of 30 candidates?
(a) 820 (b) 850 (c) 880 (d) 870.
(vi) The proposition P˄(~P˅Q) is a
(a) Tautology
(b) logically equivalent to P˄Q
(c) logically equivalent to P˅Q
(d) a contradiction.
(vii) What is the minimum number of vertices necessary for a graph with 6 edges?
(a) 6 (b) 5 (c) 7 (d) none of these.
MCAP 1104 4 MCAP 1104 1
 MCA /1st SEM/MCAP 1104/2017 MCA /1st SEM/MCAP 1104/2017
(viii) A partial ordered relation is transitive, reflexive and (c ) Find the general solution of the following recurrence relation
(a) antisymmetric (b) b
bisymmetric an+2 - 5an+1 + 6an = 4n, n ≥ 0
(c) anti reflexive (d) asymmetric
symmetric. 4+4+4
(ix) If N be the set of all natural numbers then the mapping f : N  N
defined by 5. (a) What is the number of permutations in the letters of the word
MISSISSIPPI where 4S’s do not come together?
2n, if n is even (b) Show that if any 30 people are selected, then we can choose a subset of
f(n)= is 5 so that all 5 were born on the same day of the week.
n, if n is odd
(c ) Consider a set of integers from 1 to 250. Find how many of these
numbers are divisible by 3 or 7 or 5. Also indicate how many are
(a) onto (b) o
one-to-one
divisible by 3 or 7 but not by 5 and divisible by 3 or 5.
(c) both (a) and (b) (d) n
none.
3 + 3 +(2 + 2 + 2) = 12
(x) Which of the following propositions is a tautology? Group - D
(a) (p ⋁ q )  q) (b) p ⋁ (q  p)
(c) p ⋁ (p  q) (d) b
both (b) & (c). 6. (a) Prove that the number of vertices of odd
odd-degree in a graph G is always
Group - B even.
(b) Prove that the maximum number of edges in a graph G with n vertices
2. (a) Prove that for any three sets A, B, C : A × (B C) = (A × B)  (A × C). and k components is (n - k)(n - k +1)/2. From this expression find the
maximum number of edges in a graph G with only one component.
(b) A relation ρ is defined on the set N of natural numbers such that
5 + (6 + 1) = 12
“m ρ n iff m is a divisor of n”  m, n ϵ N.
Examine if ρ is
7. (a) Draw a binary tree to represent the mathematical expression
(i) reflexive (ii) symmetric (iii) transitive.
(a - b)/(c * (d - e)).
(c) Prove that (P˄(P↔Q))→Q is a tautology.
(b) What is a Minimal Spanning Tree? Find a minimal spanning tree using
4 + (2 + 2 + 2) + 2 = 12
Kruskal’s algorithm for the following weighted graph where the
numbers represent the weight of the corresponding edge. What is the
3. (a) Consider f : Z+  Z+ defined by f (a) = a2 . Is f one-to-one?
one Is f onto?
total weight of the minimal spanning tree? Also calculate the
Explain.
complexity of the algorithm.
(b) Let f : A  B, g : B  C and h : B  C be mappings such that
(g 0 f) = (h 0 f) and f is surjective. Prove that g = h.
(c) Prove that p⋁ ( p ⋀ q) ( p ⋁ q )
4 + 4 + 4 = 12
Group – C

4. (a) Find the generating function for the sequence {7, 8, 9, 10,…….}
(b) Find the coefficient of x18 in
(𝒙 + 𝒙𝟐 + 𝒙𝟑 + 𝒙𝟒 + 𝒙𝟓 )(𝒙𝟐 + 𝒙𝟑 + 𝒙𝟒 + 𝒙𝟓 + ⋯ )5
4 + (2 + 4 + 2) = 12
MCAP 1104 2 MCAP 1104 3