Library

DBA · Deterministic Büchi

Requests and grants alternate

A request, then its grant, then the next request: never two of either in a row, no grant first, and no request left hanging. A safety part (the order) and a liveness part (the hanging request), checked by one two-state machine.

idlebusynrng
The machine as drawn — 2 states, 4 transitions.

The author’s examples, run

(n) → accept(nn) → accept(rg) → acceptnn(n) → accept(g) → reject(r) → rejectg(n) → rejectg(r) → reject