Library

NBA · ω-regular

Infinitely many a’s, and eventually no b

GF a ∧ FG ¬b. The second half needs a guess — no deterministic Büchi automaton knows when the b’s have stopped — so the machine waits, guesses the moment, and from then on loops between two states that see a’s and c’s, accepting each time an a goes by.

waitsawAquieta, b, cacacac
The machine as drawn — 3 states, 9 transitions.

The author’s examples, run

(a) → accept(aa) → accept(ac) → accept(ca) → accept(b) → reject(c) → reject(ab) → reject(ba) → reject