Library

DBA · Deterministic Büchi

Between q and r, p must happen

Existence between q and r: whenever q opens an interval, p must occur before the r that closes it. An interval left open forever imposes nothing — the pattern’s usual scope. The state remembers whether an interval is open and whether p has been seen in it.

outopendonep, r, nqq, npp, q, nr
The machine as drawn — 3 states, 11 transitions.

The author’s examples, run

(n) → accept(p) → accept(q) → accept(r) → acceptq(r) → reject(qr) → reject(rq) → rejectnq(r) → reject