NFA (nondeterministic finite automata) accepts only finite words while a NBA (nondeterministic Büchi automata) accepts infinite words (and hence $\omega-$regular languages).

I think the example automata accepts finite word like $A,B,A,B$. But it also accepts infinite words like $A,B,A,B,...$.

How can i know if the example-automata accepts the finite language $(AB)^*$ or the infinite language $(AB)^{\omega}$(is the automata an NFA or NBA)?

Can it be differed and if yes how?



1 Answer 1


It's impossible to tell if all you have is the pictorial representation, since these look the same for both types of automata. Even if you're given a formal specification you won't necessarily be able to tell the difference (it depends on how these automata are encoded).

This kind of ambiguity is similar to linguistic ambiguity that can occur in real life. For example, suppose you see the word "impossible" written on the wall. Can you tell whether it's English or French?

Sometimes this kind of ambiguity is purposeful. For example, the pictorial representation of a DFA doubles as the pictorial representation of an equivalent NFA. The only difference in your case is that the two interpretations are inequivalent.

  • $\begingroup$ I learned that every automata represents exactly one language (e.g. regular language for NFA). Does it mean i have to state if the displayed automata is an NFA oder NBA if i want to represent a language with it? $\endgroup$
    – himynameis
    Commented Jan 2, 2018 at 21:07
  • $\begingroup$ It's usually clear from context, but if it isn't, you have to specify. $\endgroup$ Commented Jan 2, 2018 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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