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$

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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