Library

NBA · ω-regular

Eventually, a and b alternate forever

From some point on the word is ababab…: the machine skips any prefix, then guesses where the alternation begins and checks it for ever. Like FG b, this needs the guess — no deterministic Büchi automaton can tell when to start looking.

skipgotAgotBa, baba
The machine as drawn — 3 states, 5 transitions.

The author’s examples, run

(ab) → accept(ba) → accept(abab) → accept(baba) → accept(a) → reject(b) → reject(aa) → reject(bb) → reject