Posts

Showing posts from April 4, 2010

TOC Question List Unit - I C

Image
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

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 orj ≤ √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

TOC Question List Unit - I A

Image
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