Thread: Proving NFA Correctness

Question:

Formally prove the correctness of the union construction as follows. Let M1 and M2 be the two -NFA's constructed for R1 and R2 and let N be the -NFA constructed so that L(N) = R1 + R2. Let w be a string such that . Prove that either or . Use induction on all strings w.

Not only do I have no idea what to do, I don't even know what this is asking. Any push in the right direction would be helpful.

Thanks.

Here is my guess about the concepts and notations. Feel free to correct.

The empty word is denoted by . A -NFA is a nondeterministic automaton that can change state without reading any symbols. R1 and R2 are regular expressions, and + denotes the union ("or") of regular expressions. probably means that the automaton N reads the word w and moves from state to state f.

You must have been given a way to construct an NFA N that accepts (L1 union L2) from two NFA's M1 and M2 that accept L1 and L2, respectively. N just has a new initial state that nondeterministically and without reading any symbols changes into either the initial state of M1 or the initial state of M2. After that it behaves like M1 or M2. You have to show that if w is accepted by N, then it is accepted by M1 or by M2 (and, presumably, the other way around).

This is kind of obvious because the only thing N can do is to become either M1 or M2, so to speak. However, to be very formal, one may need to invoke induction.