# Given NFA to recognize a language, construct a new NFA for that language without the empty string

Describe a (general) procedure that, given some finite automaton M, produces a new finite automaton M’ with: M’ rejects ε, but accepts otherwise the identical language as M does.Note that M may or may not accept ε, while M’ does not!

My solution is to discuss the different cases. If M doesn't contain ε, then, don't need to produce a new M', but if M contains ε-transition, then convert it to DFA. I'm not sure my procedure is right or not.

Can someone come up with some more effective idea?

• It's not clear what you do in the second (interesting) case. What if $M$ is already a DFA? Also, if you're not sure the procedure works, try it on something! Jun 10 '13 at 3:00
• Your approach is trivially wrong. Determinising does not change the language, so the resulting automaton still accepts the empty word. Think about how you decide algorithmically whether an automaton accepts the empty word.
– Raphael
Jun 10 '13 at 10:37
• @Raphael: I guess, the OP implied to turn the initial state of the DFA into a non-excepting state. Jun 11 '13 at 19:40

Why go for a subtle or elegant answer? You can drive a screw in with a jackhammer, too.

1. Define a DFA $M_{\epsilon}^{-1}$ for the language $\Sigma^* \setminus \{\epsilon\}$. Hint: it has two states for any $\Sigma$.
2. Say how to construct $M'$ such that $L(M') = L(M) \cap L(M_{\epsilon}^{-1})$. Hint: use the Cartesian Product Machine construction.
• If the coffeemaker already contains coffee powder, empty it, to get to a known state. Jun 11 '13 at 19:44
• @frafl Sounds exactly like the usual approach in mathematics.</banter>
– Raphael
Jun 11 '13 at 19:54
• Fun fact: if you determinise and minimise, you get the same automaton as with any other approach and worst-case runtime is not even different (assuming you want a minimal DFA).
– Raphael
Jun 11 '13 at 19:56

Hint: Duplicate the starting state.

• you mean go back to start state? Jun 10 '13 at 4:24
• I mean what I wrote. Jun 10 '13 at 13:53
• Think about it. The empty word will only get accepted in the starting state (provided you don't have any $\epsilon$-transitions). What could you do then to make it not accepted? Jul 26 '13 at 16:20