Non-deterministic Finite State Machines

The easiest kind of finite state machine (or "FSM") to understand is a deterministic FSM. With this variety, from any given state, a given event will lead to exactly one course of action -- no more, no less.

For a non-deterministic FSM, from a given state, any given event may lead, not to a single response, but to a set of potential responses. The choice among these candidates is deferred till later. Eventually, subsequent events narrow down the possibilities to single response.

The advantage of a non-deterministic FSM is that it can be more concise. You can express the possible paths with a smaller transition diagram.

The disadvantage is that it is more difficult to translate into code. One approach is to spawn another machine whenever the paths branch. All the active machines receive all input events concurrently. Whenever any machine enters an error state, it disappears. Eventually (one hopes) only one machine remains.

Anyone who wants to code such a thing in COBOL is welcome to try.

A less convoluted approach is to transform the non-deterministic FSM into an equivalent deterministic FSM. Even though the new FSM will be larger than the original, you can translate it into code in an almost mechanical manner.

[gears]Finite State Machines [block]Parsing [books]Further reading
[home]COBOL Home