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?
Why go for a subtle or elegant answer? You can drive a screw in with a jackhammer, too.


Define a DFA $M_{\epsilon}^{-1}$ for the language $\Sigma^* \setminus \{\epsilon\}$. Hint: it has two states for any $\Sigma$.
Say how to construct $M'$ such that $L(M') = L(M) \cap L(M_{\epsilon}^{-1})$. Hint: use the Cartesian Product Machine construction.