0
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • $\begingroup$ There is no such thing as a minimal NFA, well it is not unique. $\endgroup$
    – Hendrik Jan
    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$
    – Hendrik Jan
    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$
    – Yuval Filmus
    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$
    – Hendrik Jan
    Jan 20, 2017 at 14:44

0

Reset to default

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.