Library

DBA · Deterministic Büchi

Infinitely often, two a’s in a row

GF(a ∧ X a). The machine watches for aa and passes through its accepting state each time one completes. An infinite word with infinitely many a’s may still never have two together — (ab)^ω is rejected.

noneonepairababab
The machine as drawn — 3 states, 6 transitions.

The author’s examples, run

(a) → accept(aa) → accept(aaa) → accept(aab) → accept(b) → reject(ab) → reject(ba) → reject(bb) → reject