Library

NBA · ω-regular

Infinitely many a’s, or finitely many b’s

GF a ∨ FG ¬b. Nondeterminism makes a union easy: one branch is the deterministic machine for GF a, the other guesses the moment after which no b will come. The second half on its own already needs a guess.

startsawAotherquietab, cab, cab, ca, b, ca, ca, c
The machine as drawn — 4 states, 16 transitions.

The author’s examples, run

(a) → accept(c) → accept(aa) → accept(ab) → accept(b) → reject(bb) → reject(bc) → reject(cb) → reject