The question is: Prove that every NFA can be converted into one with a single accept state. Is the same true for DFAs ? Prove your answer.
I already did the first part of proving that NFA's can be converted into one with a single accept state by using the epsilons.. so the question is:
If every NFA is a DFA, the fact that I can make an NFA to a single accepting state proves that I can also do it for a DFA? is that enough?
Best Answer
First, it’s not true that every NFA is a DFA: exactly the opposite is true. (Judging by your question, this might even have been what you were actually thinking.) What you’ve already proved therefore shows that every DFA can be converted to an NFA with a single acceptor state, but it doesn’t prove that every DFA can be converted to a DFA with a single acceptor state. And in fact that statement isn’t true.
Suppose that your alphabet is $\Sigma=\{a\}$. Consider the language $L=\{\lambda,a\}$, where $\lambda$ is the empty word. (Possibly you use $\epsilon$ for the empty word.) It’s easy to design a three-state DFA that accepts this language: it has an states $q_0,q_1$, and $q_2$ and transitions
$$\begin{align*} &q_0\overset{a}\longrightarrow q_1\;,\\ &q_1\overset{a}\longrightarrow q_2\;,\text{ and}\\ &q_2\overset{a}\longrightarrow q_2\;,\\ \end{align*}$$
and states $q_0$ and $q_1$ are acceptor states. Try to prove that there is no DFA that accepts $L$ and has only one acceptor state. In case you find that you can’t, most of the argument is in the spoiler-protected block belos.