Theoretical Foundations of Computer Science Question Bank

Ankita Katdare

Ankita Katdare

@abrakadabra • Oct 22, 2024
  • 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.
Like 0 Replies 3

Replies

Welcome, guest

Join CrazyEngineers to reply, ask questions, and participate in conversations.

Sign up Log in

CrazyEngineers powered by Jatra Community Platform

  • whiz.kid.aniket

    whiz.kid.aniket

    @whizkidaniket-5IiBCq • Nov 9, 2010

    @AKD: add some more!:wink:
    0
  • Ankita Katdare

    Ankita Katdare

    @abrakadabra • Jul 13, 2011

    Please add more questions to this question bank. We can compile a PDF of those and keep it for download.
    0
  • Ankita Katdare

    Ankita Katdare

    @abrakadabra • Nov 21, 2011

    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.
    0