Library

DFA · Regular

Two processes, one critical section

A+ and A− are process A entering and leaving its critical section, B+ and B− the same for B. Accepted: traces that keep mutual exclusion and end with both outside. The state where both are inside does not exist — that is the property.

idleinAinBA+B+A-B-
The machine as drawn — 3 states, 4 transitions.Every word up to length 4, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

ε → acceptA+ A- B+ B- → acceptA+ A- → acceptB+ B- B+ B- → acceptA+ → rejectA- A- B+ B- → rejectA- A- → rejectA+ B- B+ B- → reject