0
$\begingroup$

I know that if there are no non-final states in DFA then the language accepted is $\Sigma^*$.

What will happen if there are no non-final states in an NFA? Can we say it also accepts $\Sigma^*$? Can there be an NFA with no non-final states whose minimal NFA has some non-final state?


Oh , no nonfinal states means all are final states. So DFA - all final states means every string gets accepted. So language is $\sum^*$. For NFA, it need not be $\sum^*$. Please correct me if i am wrong here. Other case --> If there are no final states(all non-final states) means in DFA, language accepted is empty language. In case of NFA with no final state means empty language right?

nfa example

$\endgroup$
  • 1
    $\begingroup$ Do you know why a DFA with no non-final states accepts $\Sigma^*$? See if the same argument works in your case. $\endgroup$ – Yuval Filmus Nov 12 at 16:52
  • 1
    $\begingroup$ I don't see where minimal automata enter the picture. The definition of the language accepted by a DFA/NFA doesn't involve them. $\endgroup$ – Yuval Filmus Nov 12 at 17:04
  • 1
    $\begingroup$ Can you give an example of an NFA with no non-final states whose language is not everything? $\endgroup$ – Yuval Filmus Nov 12 at 19:41
  • 1
    $\begingroup$ Yes, seems fine. $\endgroup$ – Yuval Filmus Nov 12 at 20:08
  • 1
    $\begingroup$ I think I gave you enough help. $\endgroup$ – Yuval Filmus Nov 12 at 20:11
1
$\begingroup$

Imagine an NFA with a single state, which is final/accepting. It has no edges.

This NFA accepts the language $\{\varepsilon\}$—that is, only the empty string. If it is given a non-empty string, it looks for appropriate edges leading away from the starting state, finds none, and fails.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.