Finite state machine
A Finite state machine (FSM) is computational abstraction which maps a finite number of states to other states within the same set, via transitions. An FSM can only be in one state at any given moment. Transitions can either be explicit or implicit; explicit transitions are triggered by an input signal and implicit transitions by the internal state of the system (that is, the current state). Implicit transitions thus represent "automatic" or sequenced states that are generally processed between explicit transitions (although they can also be used to provide an optional path when no valid transition exists for a given input signal).
Consider the model of a simple vending machine. The machine is initially in the "ready" state, which maps to exactly two states in the following way:
- ready -> deposit -> waiting
- ready -> quit -> exit
The variables in bold-face represent transitions. Any input signal not corresponding to one of those transitions can either trigger an error or be ignored. Otherwise, the current state is updated and the process is repeated. If, for example, a deposit input signal is encountered, the FSM will move to the "waiting" state, which defines these transitions:
- waiting -> select -> dispense
- waiting -> refund -> refunding
The "dispense" state defines only one transition:
- dispense -> remove -> ready
Note, however, that in this example the "refunding" state doesn't actually require input in order to move to the "ready" state, so an implicit transition is defined as such:
- refunding -> ready
Implement a finite state machine which handles both explicit and implicit transitions. Then demonstrate an example which models some real-world process.
- See also
- Computers Without Memory (Finite State Automata), A Computerphile Video.
Works with 1k of RAM.
There doesn't seem much point, in BASIC, implementing a 'general' FSM that would accept a list of states and transition rules as parameters, because an unstructured BASIC program in essence already is that list.
Within each state, if the transition is implicit we just
GOTO the next state. If it is explicit, we loop until the user presses a key corresponding to a valid transition. Invalid inputs are ignored.
100 GOTO 110 is superfluous, because it would go there anyway; but it is worth including it in case we wanted to modify the program later and transition somewhere else out of the dispense state.
Note that the program uses no variables and makes no use of the return stack: all the state is expressed in the (so to speak) state.
10 PRINT "PRESS D(EPOSIT) OR Q(UIT)"
20 IF INKEY$="D" THEN GOTO 50
30 IF INKEY$="Q" THEN STOP
40 GOTO 20
50 PRINT "PRESS S(ELECT) OR R(EFUND)"
60 IF INKEY$="S" THEN GOTO 90
70 IF INKEY$="R" THEN GOTO 140
80 GOTO 60
90 PRINT "DISPENSED"
100 GOTO 110
110 PRINT "PRESS R(EMOVE)"
120 IF INKEY$="R" THEN GOTO 10
130 GOTO 120
140 PRINT "REFUNDED"
150 GOTO 10
It will be seen that the user has pressed, in order, D, R, D, S, R, and Q.
PRESS D(EPOSIT) OR Q(UIT) PRESS S(ELECT) OR R(EFUND) REFUNDED PRESS D(EPOSIT) OR Q(UIT) PRESS S(ELECT) OR R(EFUND) DISPENSED PRESS R(EMOVE) PRESS D(EPOSIT) OR Q(UIT)
template <typename State, typename Transition = State>
std::map<State, std::map<Transition, State>>
set(State const& state)
current = state;
add(State const& state, Transition const& transition, State const& next)
database[state][transition] = next;
Add a state which is also it's own transition (and thus a link in a chain of sequences)
add(State const& state_and_transition, State const& next)
add(state_and_transition, state_and_transition, next);
process(Transition const& transition)
transitions = database[current],
found = transitions.find(transition);
if(found == transitions.end())
next = found->second;
Process so-called "automatic transitions" (ie: sequencing)
A set of utility functions that may be helpful for displaying valid transitions to the user, etc...
template <typename PushBackContainer>
get_valid_transitions(State const& state, PushBackContainer& container)
found = database.find(state);
if(found == database.end())
transitions = found->second;
if(transitions.size() == 0)
for(auto const& iterator : transitions)
transition = iterator.first;
template <typename Container>
return get_valid_transitions(get(), container);
Example usage: a simple vending machine
print(string const& message)
cout << message << endl;
machine.add("ready", "quit", "exit");
machine.add("ready", "deposit", "waiting");
machine.add("waiting", "select", "dispense");
machine.add("waiting", "refund", "refunding");
machine.add("dispense", "remove", "ready");
state = machine.get();
if(state == "ready")
print("Please deposit coins.");
else if(state == "waiting")
print("Please select a product.");
else if(state == "dispense")
print("Dispensed...please remove product from tray.");
else if(state == "refunding")
else if(state == "exit")
print("Internal error: unaccounted state '" + state + "'!");
Handle "automatic" transitions
for(auto const& transition : transitions)
options += ", ";
options += transition;
print("[" + state + "] Input the next transition (" + options + "): ");
cout << " > ";
cin >> transition;
print( "Error: invalid transition!");
Please deposit coins. [ready] Enter the next transition (deposit, quit): > deposit Please select a product. [waiting] Enter the next transition (refund, select): > refund Refunding money... Please deposit coins. [ready] Enter the next transition (deposit, quit): > deposit Please select a product. [waiting] Enter the next transition (refund, select): > select Dispensed...please remove product from tray. [dispense] Enter the next transition (remove): > remove Please deposit coins. [ready] Enter the next transition (deposit, quit): > quit