Library

DBA · Deterministic Büchi

Every request is eventually granted

G(r → F g) over requests r, grants g and idle steps n. Two states: nothing pending, or a request waiting. Büchi acceptance asks for “nothing pending” infinitely often — a request left waiting forever means the run eventually stays in the other state.

idlependingrg, ngr, n
The machine as drawn — 2 states, 6 transitions.

The author’s examples, run

(g) → accept(n) → accept(gg) → accept(gn) → accept(r) → rejectr(n) → reject(nr) → reject(rn) → reject