State Machine Diagrams

The previous lesson measured a looseness: the activity notation accepted 168 total orderings at once, and this excess was deliberate. A partial order is written precisely to be loose; what needed counting was the size of that looseness.

A state machine is not written to be loose. It claims the opposite: it lists the states an object can pass through and the transitions permitted between those states, and rejects everything else. It is a claim of exactness. This lesson tests that claim from two directions: does the machine reject a sequence that genuinely occurs in the system, and does it accept a sequence that never occurs in the system. The two errors are distinct things, are counted separately, and closing one grows the other.

A Two-Way Comparison

A work order in the shop has four states: open, allocated, scheduled, closed. Six transitions are written. This machine’s language is every event sequence that starts at the initial state and ends at the closed state; looking at sequences up to six events long, this language contains six sequences.

The number of sequences the system actually produces is also six. Because the two numbers are equal, it might seem the machine is correct. It is not — the sets are not equal, only their sizes are. There are two things that need measuring:

• Under-approximation. A sequence that occurs in the system but that the machine rejects. This means the machine holds reality too narrowly; a check written against such a machine flags a genuine work order as an error.
• Over-approximation. A sequence the machine accepts but that never occurs in the system. This means the machine holds reality too broadly; such a machine presents a path that will never happen as if it exists, and leads to code being written for that path.

"""State machine notation: under-approximation and over-approximation are
counted separately. The STATE_MACHINE, REAL_SEQUENCES, and machine_language
definitions from the shared reference are built exactly as they are there."""
from itertools import product

STATE_MACHINE = {
    "open":      {"allocate": "allocated", "cancel": "closed"},
    "allocated": {"schedule": "scheduled", "cancel": "closed"},
    "scheduled": {"process": "scheduled", "finish": "closed"},
    "closed":    {},
}
START = "open"
EVENTS = ("allocate", "schedule", "process", "finish", "cancel")

REAL_SEQUENCES = [
    ("allocate", "schedule", "process", "finish"),
    ("allocate", "schedule", "process", "process", "finish"),
    ("allocate", "schedule", "process", "process", "process", "finish"),
    ("allocate", "schedule", "process", "schedule", "process", "finish"),   # rescheduled
    ("allocate", "schedule", "cancel"),                                     # canceled before processing
    ("cancel",),
]


def machine_accepts(machine, sequence, start=START):
    state = start
    for event in sequence:
        if event not in machine[state]:
            return False
        state = machine[state][event]
    return True


def machine_language(machine, events, length, start=START):
    accepted = []
    for n in range(1, length + 1):
        for sequence in product(events, repeat=n):
            state = start
            valid = True
            for event in sequence:
                if event not in machine[state]:
                    valid = False
                    break
                state = machine[state][event]
            if valid and not machine[state]:
                accepted.append(sequence)
    return accepted


# ---- repaired machine: two transitions added
REPAIRED = {state: dict(g) for state, g in STATE_MACHINE.items()}
REPAIRED["scheduled"]["schedule"] = "scheduled"
REPAIRED["scheduled"]["cancel"] = "closed"


# ---- DD11: guarded machine. The same two transitions, with a guard condition on top.
def processed_since_last_schedule(history):
    """Has there been at least one 'process' since the state last entered 'scheduled'."""
    position = max((i for i, e in enumerate(history) if e == "schedule"), default=None)
    return position is not None and "process" in history[position + 1:]


GUARDS = {
    ("scheduled", "schedule"): processed_since_last_schedule,
    ("scheduled", "cancel"): lambda history: "process" not in history,
}


def guarded_accepts(sequence, start=START):
    state, history = start, []
    for event in sequence:
        if event not in REPAIRED[state]:
            return False
        guard = GUARDS.get((state, event))
        if guard and not guard(tuple(history)):
            return False
        history.append(event)
        state = REPAIRED[state][event]
    return True


def guarded_language(events, length, start=START):
    accepted = []
    for n in range(1, length + 1):
        for sequence in product(events, repeat=n):
            if not guarded_accepts(sequence, start):
                continue
            state = start
            for event in sequence:
                state = REPAIRED[state][event]
            if not REPAIRED[state]:
                accepted.append(sequence)
    return accepted


# ---- DD12: writing history into the STATE instead of text. "scheduled" splits in two.
SPLIT = {
    "open":       {"allocate": "allocated", "cancel": "closed"},
    "allocated":  {"schedule": "scheduled", "cancel": "closed"},
    "scheduled":  {"process": "processed", "cancel": "closed"},
    "processed":  {"process": "processed", "schedule": "scheduled", "finish": "closed"},
    "closed":     {},
}


def symbol_count(machine, guards=0):
    return len(machine) + sum(len(g) for g in machine.values()) + guards


def measure(name, language, accepts):
    over = [d for d in language if d not in REAL_SEQUENCES]
    under = [d for d in REAL_SEQUENCES if not accepts(d)]
    return {"name": name, "language": len(language), "over": len(over), "under": len(under),
            "under_list": under, "over_list": over}


D1 = machine_language(STATE_MACHINE, EVENTS, 6)
O1 = measure("four states, six transitions", D1, lambda d: machine_accepts(STATE_MACHINE, d))
print("SYSTEM  :", len(REAL_SEQUENCES), "real transition sequences")
print("NOTATION:", symbol_count(STATE_MACHINE), "symbols =", len(STATE_MACHINE), "states +",
      sum(len(g) for g in STATE_MACHINE.values()), "transitions")
print("COST    : under-approximation", O1["under"], "| over-approximation", O1["over"])
print()
for d in O1["under_list"]:
    print("  REJECTED:", " ".join(d))
for d in O1["over_list"]:
    print("  OVER-ACCEPTED:", " ".join(d))
print()
D2 = machine_language(REPAIRED, EVENTS, 6)
O2 = measure("two transitions added", D2, lambda d: machine_accepts(REPAIRED, d))
D3 = guarded_language(EVENTS, 6)
O3 = measure("two transitions + two guard conditions", D3, guarded_accepts)
D4 = machine_language(SPLIT, EVENTS, 6)
O4 = measure("five states, nine transitions", D4, lambda d: machine_accepts(SPLIT, d))
print(f"{'machine':40s} symbols  accepted  under  over")
for o, s in ((O1, symbol_count(STATE_MACHINE)), (O2, symbol_count(REPAIRED)),
             (O3, symbol_count(REPAIRED, 2)), (O4, symbol_count(SPLIT))):
    print(f"{o['name']:40s} {s:5d} {o['language']:6d} {o['under']:6d} {o['over']:6d}")
print()
print("over-approximation depends on the length window")
print("window  six-transition  eight-transition  guarded  split-state")
for u in (4, 5, 6, 7, 8):
    a = len([d for d in machine_language(STATE_MACHINE, EVENTS, u)
             if d not in REAL_SEQUENCES])
    b = len([d for d in machine_language(REPAIRED, EVENTS, u) if d not in REAL_SEQUENCES])
    c = len([d for d in guarded_language(EVENTS, u) if d not in REAL_SEQUENCES])
    e = len([d for d in machine_language(SPLIT, EVENTS, u) if d not in REAL_SEQUENCES])
    print(f"{u:7d} {a:11d} {b:16d} {c:9d} {e:13d}")
print()
print("the guarded machine's over-approximation:", [" ".join(d) for d in O3["over_list"]])
print("the split-state machine's over-approximation:", [" ".join(d) for d in O4["over_list"]])

SYSTEM  : 6 real transition sequences
NOTATION: 10 symbols = 4 states + 6 transitions
COST    : under-approximation 2 | over-approximation 2

  REJECTED: allocate schedule process schedule process finish
  REJECTED: allocate schedule cancel
  OVER-ACCEPTED: allocate cancel
  OVER-ACCEPTED: allocate schedule finish

machine                                  symbols  accepted  under  over
four states, six transitions                10      6      2      2
two transitions added                       12     32      0     26
two transitions + two guard conditions      14     10      0      4
five states, nine transitions               14      9      0      3

over-approximation depends on the length window
window  six-transition  eight-transition  guarded  split-state
      4           2                5         2             1
      5           2               12         3             2
      6           2               26         4             3
      7           3               58         9             8
      8           4              122        17            16

the guarded machine's over-approximation: ['allocate cancel', 'allocate schedule finish', 'allocate schedule process schedule finish', 'allocate schedule process process schedule finish']
the split-state machine's over-approximation: ['allocate cancel', 'allocate schedule process schedule cancel', 'allocate schedule process process schedule cancel']

Three numbers: the system has 6 real sequences, the notation has 10 symbols, the cost is 2 cases of under-approximation and 2 of over-approximation.

The Two Rejected Sequences

The two sequences the machine rejects genuinely happen in the shop. The first is rescheduling: after a work order is processed, a problem turns up, the work is rescheduled, and processed again. The machine has no transition from the scheduled state back to the scheduled state, so the second schedule event is rejected.

The second is cancellation before processing begins. The machine accepts cancellation only in the open and allocated states; there is no cancel path from the scheduled state. Yet a work order that has been scheduled but not yet processed can, in fact, be canceled.

What the two cases of under-approximation share is that both are invisible. The machine does not say it is wrong; it only does not accept those sequences. Someone looking at the diagram cannot notice the gap, because what is missing is not drawn in the diagram. It only comes to light once the list of real sequences is held and tested against the machine one at a time — which is exactly what this lesson does.

The two over-accepted sequences are drawn the same way but do not occur in reality. Canceling directly after stock is allocated, and finishing without any processing at all after scheduling, are paths the machine permits; neither happens in the shop.

The Cost of Repairing

The way to rescue the two rejected sequences is clear: add two transitions to the scheduled state. One is schedule from scheduled to scheduled, the other is cancel from scheduled to closed. The notation rises from 10 symbols to 12. Under-approximation drops to 0 — both real sequences are now accepted.

Over-approximation, however, rises from 2 to 26. Thirteen times. The machine’s language grows from six sequences to 32, and all of the growth comes from sequences with no counterpart in the system.

The reason is structural. Adding a self-loop schedule transition to the scheduled state does not say “it can be rescheduled after processing”; it says “it can be rescheduled at any moment while in the scheduled state, any number of times.” A state machine keeps no history; the only thing it keeps is the state it is currently in. Once a transition is added, that transition becomes open after every path by which the state can be reached. It is added for one intended path and opens up for every path obtained.

The rule that follows is this: the price of closing under-approximation is over-approximation. The two errors sit in opposite directions, and no notation can bring both to zero at once — if it could, the notation would be the system itself, not a projection of it. For this reason, a single number is not enough when evaluating a state machine; two numbers are written side by side.

A Guard Condition Narrows the Cost

The notation has a tool against this situation: the guard condition. A condition is written on a transition, one that can only be taken once it is satisfied. Let two guard conditions be added to the two new transitions (DD11): rescheduling can only be taken if at least one processing has happened since the scheduled state was entered; cancellation can only be taken if no processing has happened at all.

The result is in the table: 14 symbols, under-approximation still 0, over-approximation drops from 26 to 4. Twenty-two wrong sequences were closed off for the price of two symbols.

Two of the remaining four were already there from the start — canceling directly after allocating stock, and finishing without any processing after scheduling. So the net over-approximation brought in by the two transitions and two guard conditions is 2, and both of these are the case of rescheduling and then finishing without any processing. A guard condition does not zero out the cost, it narrows it.

Narrowing has its own cost too. A guard condition is text; it does not sit in the structure of the state graph but as a sentence written on the transition. The machine’s structure does not test it — what tests it is the code that reads the condition and implements it. The notation wrote two more symbols but moved testability from the graph into text, and a constraint written as text can be wrong. Indeed, that is exactly what happens here: the written condition does not prevent finishing directly after rescheduling.

Writing History into the State Instead of Text

What the guard condition is doing is, in fact, remembering history: the question “has there been processing since I entered the scheduled state” asks for information the state does not carry. There is a second way to carry this information — turn it into a state.

The scheduled state is split in two (DD12): scheduled for work that has been scheduled but not yet processed, processed for work that processing has begun on. Cancellation can only be taken from the scheduled state, finishing only from the processed state; rescheduling goes from the processed state back to the scheduled state. The result is five states and nine transitions, that is, 14 symbols — exactly the same number as the guarded machine.

The measurement comes out better in two places. Under-approximation is still 0, over-approximation is 3 instead of 4. What is more, one of the remaining three was already there from the start, and the two sequences the guarded machine could not close — rescheduling and then finishing without any processing at all — are closed structurally here: there is no finish transition out of the scheduled state. On the other hand, the split machine accepts cancellation after rescheduling, and this sequence does not happen in the shop.

The real difference is not in the count but in where the constraint sits. In the split machine, the rule is in the graph itself: whether a transition exists can be seen by looking. In the guarded machine, the rule is a sentence, and whether that sentence is read correctly and implemented correctly cannot be understood by looking at the graph. The same 14 symbols sit in two different places; one in the notation’s testable part, the other in its untestable part.

The Number Depends on the Window

The table in the middle carries a warning. A machine’s language is, in most cases, infinite — the process loop in the scheduled state produces a sequence at every length. For this reason “over-approximation 26” is not an absolute number; it is a value counted within the window of sequences of at most six events.

As the window grows, all four machines grow, but at different rates. The base six-transition machine gives 2, 2, 2, 3, 4 across the window from 4 to 8; the eight-transition machine gives 5, 12, 26, 58, 122; the guarded machine gives 2, 3, 4, 9, 17; the split-state machine gives 1, 2, 3, 8, 16. The base machine stays narrow and so grows slowly; the repaired machine opens new paths at every length and so grows fast.

What this means for comparison is that two machines’ over-approximation can only be compared within the same window, and an over-approximation number given without its window cannot be read. What the denominator is to a coverage ratio, the window is to over-approximation.

Summary

• A state machine can be wrong in two directions at once: under-approximation is rejecting what occurs in the system, over-approximation is accepting what does not. The two numbers are written separately; the language and the real sequence count being equal does not show the machine is correct.
• The four-state, six-transition machine, with 10 symbols, rejects 2 of the shop’s 6 real sequences (rescheduling, and canceling before processing) and accepts 2 sequences that do not occur in the system.
• Adding two transitions brings under-approximation down to 0 but raises over-approximation from 2 to 26: thirteen times. Because a state machine keeps no history, an added transition opens after every path by which the state is reached.
• The price of closing under-approximation is over-approximation. No single notation can zero out both errors at once; if it could, it would be the system itself, not a projection.
• Two guard conditions bring over-approximation from 26 down to 4 with 14 symbols; splitting the scheduled state in two brings it down to 3 with the same 14 symbols. The difference is not in the count but in whether the constraint sits in the graph or in text.
• The over-approximation count depends on the length window: as the window grows from 4 to 8, the base machine goes from 2 to 4, the repaired machine from 5 to 122, the guarded machine from 2 to 17, the split machine from 1 to 16. An over-approximation number given without its window cannot be read.

Next Step

This topic counted four notations of behavior. The use case notation deliberately dropped internal steps and failed to distinguish 128 systems; the sequence notation showed one of 24 traces; the activity notation accepted 168 total orderings at once; the state machine was wrong in both directions at once. What the four share is that each tries to show the system’s side in time.

The next topic does not discuss time at all. It asks what a system stores: what entities exist, what attributes they carry, what relationships are established between them. The conceptual model states 26 facts for the repair shop: 5 entities, 12 attributes, 4 relationships, 5 constraints. How these 26 facts behave when brought down to a schema reveals a different kind of loss than the behavioral notations showed — the model does not only forget, it also invents, and the two are counted separately.