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$ – Hendrik Jan Jan 20 '17 at 9:44
  • 1
    $\begingroup$ Why be so modest? I think at most two final states for an NFA will work. $\endgroup$ – Hendrik Jan Jan 20 '17 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 '17 at 9:49
  • 1
    $\begingroup$ @HendrikJan Or even just one... $\endgroup$ – Yuval Filmus Jan 20 '17 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$ – Hendrik Jan Jan 20 '17 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.