Library

DBA · Deterministic Büchi

Infinitely often a

GF a, the canonical Büchi condition: accept the infinite words with infinitely many a’s. Two states — the last letter was a, or it was not — and acceptance asks for the first one again and again. Its mirror image FG b is the standard language no DBA can recognise.

waitingsaw abaab
The machine as drawn — 2 states, 4 transitions.

The author’s examples, run

(a) → accept(b) → reject(ab) → accepta(b) → rejectb(a) → acceptabab(ab) → accept