# Generalized Büchi Automata - Formal definition of a state appearing infinitely often?

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.

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?

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.

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