# NFA that ends with 0 and doesn't have 11 after the first 0

So as the title says i m trying to find this NFA. So far i thought to make an NFA that "guesses" what comes after the first 0 and i got this:

After some time trying to get rid of all the extra (7 !) states i put in i got to this beauty:

But now i cant figure out how to get rid of the one extra state. Also if you have any tips on how to go to simpler NFA's instead of what i did (like a thought process for this problem) i would appreciate it a lot. Thank you

In your specific case: remove the $$\epsilon$$ transition and merge state $$2$$ with state $$5$$.
• There is no known efficient algorithm to convert a DFA to an equivalent minimal NFA. In fact this problem is PSPACE-hard. An algorithm in PSPACE is the following: minimize your DFA and let $n$ be the number of states of the resulting DFA. Consider all the (at most $(|\Sigma|+1)^{(n-1)(n-2)} \cdot 2(n-1)^2$) NFAs with up to $n-1$ states (guess the transitions, the number of final states and whether the initial state is final). Check if the language accepted by any of them matches the language of your DFA (this is in P). – Steven May 30 at 12:32