Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

While going through certain problems. it seems that more than one NFA is possible for the given language. Is it so?

For example for drawing: NFA ending with 1 where $\Sigma=\{0,1\}$ is

From Wikipedia page on NFA

and also we can draw one without 0 from the edge P to P!

Which one should be considered "more" correct?

share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

There are many, many different NFAs accepting a particular language, or DFAs for that matter. You can just add branches that lead into dead ends at will, for example. Or add detours that give the same result as the main road, like in your automaton adding a new state $r$, with transitions from $p$ to $r$ on 1, and then from $r$ to $r$ on 0 and 1, and finally from $r$ to $q$ on 1.

In the given case, omitting the transition from $p$ to $p$ on 0 gives another language. You should convince yourself that the modified NFA doesn't accept anything containing zeros.

share|improve this answer
Not just many -- infinitely many! –  David Richerby Feb 11 at 8:35
@DavidRicherby How many DFA exist? For many problems I could find only one –  user5507 Feb 11 at 10:56
@user5507 For DFA as well, infinitely many. But only countably many... For instance, you could just add a new state $q$ and loops $q \xrightarrow{a} q$, for each letter $a$, and then repeat the operation as long as you want... –  J.-E. Pin Feb 11 at 11:03
@user5507 If the corresponding regular expression contains a *, there are infinitely many automata because, for example, $a*$ is the same thing as $a+aaa*$, $a+aa+aaaa^*$, $a+aa+aaa+aaaaa^*$, and so on. If the corresponding regular expression has no stars then there's probably only one DFA if you insist that every state is reachable. If you allow unreachable states, you can just add states that are unreachable from the start state, so don't change the accepted language. –  David Richerby Feb 11 at 13:58
add comment

There is no notion of "more correct" so your inverted commas around "more" are well placed. An analogous question would be something like, "There are many different ways of writing a given program – which is 'most' correct?"

In theoretical terms, any automaton that accepts a language is as good as any other. The existence of an automaton means the language is regular; non-existence means it isn't.

In practical terms, there may be a preference for the automaton with the least number of states, since that requires less memory to implement.

For teaching purposes, there may be a preference for automata with simple structure and states whose "function" is easily described. For example, suppose you're asked to produce an automaton for $(a+b)^*(ab)^+$. It's much easier to describe the three-state nondeterministic automaton that "guesses" when the $(a+b)^*$ part of the string ends and then checks that the rest of the string matches $(ab)^+$ than it is to describe the corresponding deterministic automaton.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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