# Does for every NFA $N$ exist NFA $M$ that has maximum 3 final states and $L(N) = L(M)$

I have a question:

Does for every NFA $N$ exist NFA $M$ that has maximum 3 final states and $L(N) = L(M)$. I can answer no for DFA for below language and its minimal DFA that has 4 final states .

$L_1 = \{ax_1,bx_2,cx_3,dx_4 | x_1 \in \Sigma^* ,x_2 \in (a+b)^*,x_3 \in (b+c)^* ,x_4 \in (a+b+c)^*\}$ , $\Sigma = \{a,b,c,d\}$

but because there isn't any specific algorithm for finding minimal NFA,I don't know how to answer this question.can any one help ? it seems that answer is no.

• There is no such thing as a minimal NFA, well it is not unique. – Hendrik Jan Jan 20 '17 at 9:44
• Why be so modest? I think at most two final states for an NFA will work. – Hendrik Jan Jan 20 '17 at 9:45
• @HendrikJan: Do you think that 2 final state for NFA is enough?how can you say when you don't know NFA minimal? – haleh Jan 20 '17 at 9:49
• @HendrikJan Or even just one... – Yuval Filmus Jan 20 '17 at 13:43
• @Yuval I believe that without $\varepsilon$-transitions the empty string has to get its own final state when it belongs to the language. So two final states in that case. – Hendrik Jan Jan 20 '17 at 14:44