Finish the proof of the Theorem below You have to prove that

Finish the proof of the Theorem below. You have to prove that if w is a string accepted D, where D is a DFA that results from NFA N by the subset construction then there is a string v ( {}) such that v is accepted by N and w = v. (These instructions will make more sense after you work through and understand the part of the proof that has been given below.)

Theorem 2.2: Let N with alphabet be an NFA possibly with -transitions and let D be the DFA with alphabet obtained from N by the subset construction. Then N and D accept exactly the same set of strings in .

Proof: To prove this theorem we will first prove a lemma, a helping theorem from which we can easily prove the main theorem. (Actually the lemma is equivalent to the main theorem in a seemingly more detailed form.)

Lemma 2.1: For every path labeled by a nonempty string w ( {}) in N from state A to state B, there is a path in D from any state that includes A to some state that contains B that is labeled by w, where w is obtained from w by removing all occurrences of from w. (Remember that states of D are -closed sets of states of N.)

Proof of Lemma: We will prove this lemma by induction on the length (denoted by |w|) of w. (The argument informally resembles a recursive program.)

Suppose |w| = 1. Then w ( {}). If w = , then B is in the -closure of A. Therefore, since the states of D are -closed, any state of D that contains A also contains B. w is the empty string (empty! - not even an occurrence of in it; although denotes the empty string in , itself is a length 1 string in ({}).) Therefore, w labels a path from any state of D that contains A to that same state that must include B. Else, w . Let A be any state of D that contains A. Then by the subset construction, there is a path labeled by w from A to some state that contains B. (That’s how the states of D in the subset construction are determined.)

Suppose |w| = n + 1 for a fixed but arbitrary n N. The induction assumption is that for any u ({}) of length n that labels a path from state A in N to state B in N, there is a path in D from any state that contains A to some state in D that contains B and that is labeled by u. For some length n string v ({}), w = va where |v| = n, v ({}) and a ({}). va = va. Therefore, there is a path in N from state A to some state C in N labeled by v and a path from C to B labeled by the single symbol a. By the induction assumption, v labels a path from any state in D that contains A to some state X in D that contains C. By the definition of the subset construction, there is a length 1 path labeled by a in D from X to some state that contains B. Therefore there is a path in D from each state that contains A to some state that contains B.

We also have to prove the converse that any string accepted by D is with suitable ’s inserted accepted by N; more precisely: for any string u that is accepted by D there is a string w ( {}) that is accepted by N and u = w. We proceed by induction on the length of utoprovethatifXandY arestatesofDandulabelsapathfromXtoY andstateBof N is a member of Y , then there is a path in N from some state A of N that is a member of X to B.

First, by the subset construction, if in D there is transition (i.e. a length 1 path) from a stateP toastateQlabeledbya,thenforeachstateT ofNthatisamemberofQ, there is some state T of N (possibly T itself) that is a member of Q and a state S of N that is a member of P such that T is in the -closure of T and there is a length 1 path from S toT inNlabeledbya. If X is the initial state of D then there is a path in N labeled by ’s from the initial state of N to S, or S itself is the initial state of N.

The induction argument can now proceed.

Solution

Theorems, Lemmas, and Propositions----

I There are many correct mathematical statements, but not all
of them called theorems

I Less important statements that can be proven to be correct
are propositions

I Another variation is a lemma: minor auxiliary result which
aids in the proof of a theorem/proposition

I Corollary is a result whose proof follows immediately from a
theorem or proposition

I¸sl Dillig, CS243: Discrete Structures Mathematical Proof Techniques 5

Mathematical----

I Important mathematical statements that can be shown to be
true are theorems
I Many famous mathematical theorems, e.g., Pythagorean
theorem, Fermat’s last theorem
I Pythagorean theorem: Let a, b the length of the two sides of
a right triangle, and let c be the hypotenuse. Then,
a
5 + y
5 = z
5
I Fermat’s Last Theorem: For any integer n greater than 5, the
equation a
n + b
n = c
n has no solutions for non-zero x, y, z.

////General Strategies for Proving Theorems
///

Many different strategies for proving theorems:

I Direct proof: p q proved by directly showing that if p is
true, then q must follow

I Proof by contraposition: Prove p q by proving ¬q ¬p
I Proof by contradiction: Prove that the negation of the
theorem yields a contradiction

I Proof by cases: Exhaustively enumerate different possibilities,
and prove the theorem for each case

In many proofs, one needs to combine several different strategies!

///Direct Proof

I To prove p q in a direct proof, first assume p is true.
I Then use rules of inference, axioms, previously shown
theorems/lemmas to show that q is also true
I Example: If n is an odd integer, than n
2
is also odd.
I Proof: Assume n is odd. By definition of oddness, there must
exist some integer k such that n = 2k + 1. Then,
n
2 = 4k
2 + 4k + 1 = 2(2k
2 + 2k) + 1, which is odd. Thus, if
n is odd, n
2
is also odd.