Library

DBA · Deterministic Büchi

Both a and b, infinitely often

GF a ∧ GF b. Büchi acceptance names one set to visit infinitely often, so two conditions are chained: wait for an a, then for a b, and pass through the accepting state each time both have happened. The same trick turns any generalised Büchi condition into an ordinary one.

wantAwantBbothab, cba, cab, c
The machine as drawn — 3 states, 9 transitions.

The author’s examples, run

(ab) → accept(ba) → accept(aab) → accept(aba) → accept(a) → reject(b) → reject(c) → rejecta(a) → reject