If you have a DFA M, how do you construct a new NFA that accepts L(M) and {e}?

Question

Suppose you're given a DFA $M$ with a 5 tuple of $(Q, \Sigma, \delta, q_0, F)$.

How do you construct an NFA that accepts $L(M)$ and $\{\varepsilon\}$, the set containing the empty string? I know that a DFA is an NFA.

My thought is that you would simply add a new transition from the start state to the accepting state, which takes epsilon/the empty string.

For example (eps. is epsilon/empty string):

Since I've added an empty string transition, the machine is no longer a DFA, but it is an an NFA.

Answer 1

You've got the right idea, but there's a slight bug. If you add an $\varepsilon$-transition from the start state to all accepting states, then the new machine recognizes a subtly different language. Let $L_k = \{w_1 \cdots w_k : \exists u_1, \dots, u_{k-1} \in L(M) \text{ such that } w_1 u_1 w_2 \cdots u_{k-1} w_k \in L(M)\}$. Note that $L_1 = L(M)$. This new machine will recognize the union of the $L_k$, i.e., it recognizes $\bigcup_{k=1}^{\infty} L_k$.

Instead, you can create a new state $q_{\text{empty}}$, add an $\varepsilon$-transition from $q_0$ to $q_{\text{empty}}$, and take the new set of accepting states to be $F \cup \{q_{\text{empty}}\}$.