# Theoretical Foundations of Computer Science Question Bank

Discussion in 'Computer Science | IT | Networking' started by AbraKaDabra, Nov 9, 2010.

Message Count:
8,837
+1,159
Engineering Discipline:
Computer Science
• Explain Equivalence relation & Digitalization with suitable Example.
• Construct a DFA with reduced states equivalent to the regular expressions: 10 + (0 + 11) 0 * 1
• Explain Prefix, suffix, proper prefix and proper suffix of a string with suitable Example.
• Is it possible for two distinct sets A and B to satisfy the equation A X B=B X A? If so, under what circumstances? Give reason for your answer.
• Is it possible for two distinct sets A and B to satisfy A X B B X A? If so, under what circumstances? Give reason for your answer.
• Construct a FA, which does not contain ‘101’ and further minimize it.
• Write a short note on Derivation Trees.
• Write a short note on Application of Pumping Lemma
• Write a short note on Regular expression.

Message Count:
444
+46
Engineering Discipline:
Computer Science

Message Count:
8,837
+1,159
Engineering Discipline:
Computer Science

Message Count:
8,837
+1,159
Engineering Discipline:
Computer Science
1. Prove the Distributive and De Morgan’s laws for logic.
2. Give a direct proof for the following: Suppose x is an integer. Prove that if x is odd, then x+1 is
even.
3. Prove the following, using the proof by cases method: Suppose x is a real number, then -|x| ≤ x ≤
|x|.
4. Prove the following, using the proof by contradiction method. Suppose x and y are odd integers,
then xy is odd.
5. What, if anything, is wrong with the following proof:
Suppose that m is an integer. Prove that if m
2
is odd, then m is odd.
Proof:
Assume m is odd. Then m = 2k+1 for some integer k. Therefore m
2
= (2k+1)
2

=4k
2
+4k+1 = 2(2k
2
+2k) +1, which is odd. Therefore if m
2
is odd, then m is odd.
6. Given the premises s→(o∧r) and n∧¬o prove (using the rules of inference) the conclusion that ¬s.
Be sure to label your steps and give the rules of inference you are using.
7. Given the premise ∃x(p(x)∧q(x)) prove (using the rules of inference ) the conclusion that ∃x
p(x)∧∃x q(x). Be sure to label your steps and give the rules of inference you are using.