Theorem 2.2: Let N with alphabet be an NFA possibly with -transitions and let D

Question

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

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 ( {}) 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 that contains B. For some length n string v ( {}) , w = va where |v| = n, v ( {}) and a ( {}). va = v a. Therefore, there is a path in N from state A to some state C in N labeled by a v and a path from C to B labeled by the single symbol a. By the induction assumption

Let w be accepted by N. Then, there is a path in N beginning in A1, the initial state of N, through the sequence of states A1, . . . , An of N and ending at An labeled by w.

Explanation / Answer

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 ( {}) 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 that contains B. For some length n string v ( {}) , w = va where |v| = n, v ( {}) and a ( {}). va = v a. Therefore, there is a path in N from state A to some state C in N labeled by a v and a path from C to B labeled by the single symbol a. By the induction assumption

Let w be accepted by N. Then, there is a path in N beginning in A1, the initial state of N, through the sequence of states A1, . . . , An of N and ending at An labeled by w

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.