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

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.

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}}\}$$.
• I previously made a mistake in determining the language accepted by your proposed construction; see the updated answer for a correct description of what happens when you add an $\varepsilon$-transition from the start state to the final states. My previous answer implicitly assumed there were no transitions leading back to the start state. Sep 24, 2019 at 13:00