1
$\begingroup$

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):

enter image description here

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

$\endgroup$
3
$\begingroup$

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}}\}$.

$\endgroup$
  • $\begingroup$ This is an important distinction, particularly to a beginner. Thank you for pointing it out. $\endgroup$ – J. Cash Sep 24 at 4:29
  • $\begingroup$ 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. $\endgroup$ – Robert Andrews Sep 24 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.