I am studying generalized Büchi automata and I don't really understand when a state is considered to appear infinitely often. The definition I have is:

A state $s$ appears infinitely often if there exists an infinite set of points $i \in N$ such that the $i$th state of the execution is $s$.

But there's also an example which I think contradicts this definition.

enter image description here

According to the example, the language accepted by this automaton is the language where the string $ab$ appears infinitely often.

Why isn't it just $a$ appearing infinitely often? State 2 would be reached even if we only had $a$ as input. Which is wrong, the example or the definition? Or did I misunderstand the definition?


1 Answer 1


The definition and example are both correct.

If the automaton reads $a$ in state $2$ or reads $b$ in state $1$, then it rejects, because it has no state to go to. So, if the machine reads an infinite amount of its input, then it must read $a$ every time it is in $1$ and read $b$ every time it is in $2$. If the machine reads $b$ only a finite number of times, it only enters $2$ a finite number of times, so it must reject. Therefore, any string that's accepted must contain an infinite number of $b$s. Since $b$s can only be read in state $2$ and the only way of getting there is to read an $a$ from state $1$, any accepted string must contain an infinite number of $ab$s.

  • $\begingroup$ Is your first sentence a mistake? The example says the same thing you said: the accepted strings contain an infinite number of $ab$s. $\endgroup$
    – devil0150
    Jun 11, 2017 at 15:10
  • $\begingroup$ @devil0150 Good point. :-) $\endgroup$ Jun 11, 2017 at 15:11

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.