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.

  • $\begingroup$ There is no such thing as a minimal NFA, well it is not unique. $\endgroup$ Jan 20, 2017 at 9:44
  • 1
    $\begingroup$ Why be so modest? I think at most two final states for an NFA will work. $\endgroup$ Jan 20, 2017 at 9:45
  • $\begingroup$ @HendrikJan: Do you think that 2 final state for NFA is enough?how can you say when you don't know NFA minimal? $\endgroup$
    – haleh
    Jan 20, 2017 at 9:49
  • 1
    $\begingroup$ @HendrikJan Or even just one... $\endgroup$ Jan 20, 2017 at 13:43
  • 1
    $\begingroup$ @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. $\endgroup$ Jan 20, 2017 at 14:44


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.