CSC 341: February 2, 2007

In some textbooks on automata theory, the authors present a model of computation similar to Sipser's NFAs, but without $\varepsilon$ -transitions. It turns out that this model is equivalent to Sipser's NFAs, in the sense that exactly the same languages can be recognized in either model. How might one prove this?
Why is it necessary, in the proof of Theorem 1.47, to change the accept states of $N 1$ into non-accept states? No such change is made in the apparently similar proofs of Theorem 1.45 and Theorem 1.49.
In the construction that Sipser develops in his proof of Theorem 1.49, what happens if the original NFA $N 1$ has no accept states? What language does the star-NFA recognize in such a case?

One way to prove this would be to prove that the given model of computation is equivalent to DFAs. Since NFAs and DFAs are already shown to be equivalent, by the transitive property NFAs would be equivalent to this alternate model.
In Theorem 1.47 it's essential to change the accept states of $N 1$ into non-accept states because if those states were left as accept states then $N$ would also accept the strings in the language of $N 1$ , which is not what $N$ is supposed to do. $N$ is supposed to recognize the concatenation of the languages of $N 1$ and $N 2$ , which may not include all members of $N 1$ unless $N 2$ accepts the empty string.
In Theorem 1.49, if $N 1$ has no accept states then the language of $N$ is $\{\varepsilon\}$ .