Friday, April 9, 2010

TOC Question List Unit - I C

MCA SEM II
Subject Code: 620007
     Subject Name: Theory of Computation
UNIT – I
Question List - C

Q.1
(a)
Attempt Followings with Example.
5


(i)    {Λ} Vs. {ø}



(ii)   Lemma



(iii)  Quantifiers



(iv)  Equivalence Class



(v)   Power Set


(b)
Give Difference : Weak Induction Vs. Strong Induction
Prove that for every n ≥ 2,

5
Q.2
(a)
Define and Prove The Well Ordering Principle for Natural Numbers.
5

(b)
The language L is Subset of {0,1}* is defined as follows:
1. 0 є L
2. For any x  є L, 0x є L
3. For any x and y in L, all the strings 1xy, x1y, and xy1 are in L
4. No other strings are in L.
Prove that every element of L has more 0’s than 1’s Using Structural Induction.
5


OR


(b)
Define Course of Values Induction.
Prove that for any n ≥ 4,  n! > 2n.

5

TOC Question List Unit - I B

MCA SEM II
Subject Code: 620007
     Subject Name: Theory of Computation
UNIT – I
Question List - B

Q.1
(a)
Attempt Followings with Example.
5


(i)    Logical Connectives



(ii)   Surjection



(iii)  Partition of a Set



(iv)  Pigeonhole Principle



(v)   Λ Vs. ø


(b)
Give the Difference: Direct Proof Vs. Indirect Proof
For any positive integers i, j and,
if i * j = n then either i ≤ √n or  j ≤ √n
5
Q.2
(a)
Explain Structural Induction.
The Length of a function can be defined as follow.
(1) | Λ |=0
(2) For any x є Σ* and any a є Σ,
     |x a| = |x| + 1
Prove that for every x and y in Σ*, |x y| = |x| + |y|
5

(b)
Write Down the Principle of Complete Induction. Prove P(n):n is either Prime or a Product of two or more Primes, for n≥2.
5


OR


(b)
Suppose a and b are integers with 0 ≤ a ≤ b. Prove that for every n≥1,
bn – an is divisible by b-a.
5

TOC Question List Unit - I A

MCA SEM II
Subject Code: 620007
     Subject Name: Theory of Computation
UNIT – I
Question List - A

Q.1
(a)
Attempt Followings with Example.
5


(i)    Pairwise Disjoint



(ii)   Tautology



(iii)  Partial Relation



(iv)  Corollaries



(v)   Σ* Vs. Σ+


(b)
Give the Difference:
Proof by Contrapositive Vs. Proof by Contradiction
Prove √2 is irrational.
5
Q.2
(a)
What is Proof? Explain Direct Proof Method.
5

(b)
Explain Recursive Definition.
Suppose we define a real-valued function f on the natural numbers as
Follows: f(0)=0,
             for n>0, f(n) = √1+f(n-1)
Prove that for every n≥0, f(n)<2
5


OR


(b)
Write Down the Principle of Weak Induction.
Prove that for every n>0
5