Formal Languages and Automata Theory

Appendix B

FREQUENTLY ASKED UNIVERSITY QUESTIONS WITH SOLUTIONS

PART A - Brief Questions

1. What is the proof by contradiction?

   Ans: In a proof by contradiction we assume, along with the hypotheses, the logical negation of the result we wish to prove, and then reach some kind of contradiction. Principle of Contradiction is as follows.

   If we want to prove “If P, Then Q”

   1. We assume P and Not Q.
   2. We arrive at some conclusion contradicting one of our assumptions, or something obviously untrue for Not Q.
   3. This contradicts our assumption for P and Not Q.
2. Define ε - closure(q) with an example.

   Ans: Epsilon Closure of a state is simply the set of all states we can reach by following the transition function from the given state that are labeled ε. This ...