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

Improve this question
$\endgroup$
11
  • 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, 2019 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, 2019 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, 2019 at 19:41
  • 1
    $\begingroup$ Yes, seems fine. $\endgroup$
    – Yuval Filmus
    Nov 12, 2019 at 20:08
  • 1
    $\begingroup$ I think I gave you enough help. $\endgroup$
    – Yuval Filmus
    Nov 12, 2019 at 20:11

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

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.

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