Finite state machine

Finite state machine is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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).

Example

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

Task

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.

BASIC

Sinclair ZX81 BASIC

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.

The line 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.

<lang basic> 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</lang>

Output:

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)

C

This is an unapologetic implementation of goto. There have been a lot of curse words and obituaries written about it and the inventors of Java were glad to exclude it from the language, but to be fair, goto is one of the many things C inherited from languages such as Assembly or BASIC that make it truly awesome, especially when it comes to such requirements. After all, can there be a clearer and simpler implementation of a Finite State Machine (not counting BASIC ) ? <lang C> /*Abhishek Ghosh, 25th October 2017*/

1. include<stdio.h>

int main() { char str[10];

ready: do{ printf("\nMachine is READY. (D)eposit or (Q)uit :"); scanf("%s",str); }while(!(str[0]!='D'||str[0]!='d'||str[0]!='q'||str[0]!='Q'));

if(str[0]=='q'||str[0]=='Q') goto quit; goto waiting;

waiting: do{ printf("(S)elect product or choose to (R)efund :"); scanf("%s",str); }while(!(str[0]!='s'||str[0]!='S'||str[0]!='r'||str[0]!='R'));

if(str[0]=='s'||str[0]=='S'){ printf("Dispensing product..."); goto dispense; }

else{ printf("Please collect refund."); goto ready; }

dispense: do{ printf("\nPlease (C)ollect product. :"); scanf("%s",str); }while(!(str[0]!='c'||str[0]!='C'));

goto ready;

quit: printf("Thank you, shutting down now.");

return 0; } </lang> Machine simulation :

C:\rosettaCode>fsm.exe

Machine is READY. (D)eposit or (Q)uit :D
(S)elect product or choose to (R)efund :S
Dispensing product...
Please (C)ollect product. :C

Machine is READY. (D)eposit or (Q)uit :D
(S)elect product or choose to (R)efund :R
Please collect refund.
Machine is READY. (D)eposit or (Q)uit :Q
Thank you, shutting down now.

C++

<lang C>

1. include <map>

template <typename State, typename Transition = State> class finite_state_machine { protected: State current; std::map<State, std::map<Transition, State>> database; public: finite_state_machine() { set(State()); } void set(State const& state) { current = state; } State get() const { return current; } void clear() { database.clear(); } void 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)

• /

void add(State const& state_and_transition, State const& next) { add(state_and_transition, state_and_transition, next); } bool process(Transition const& transition) { auto const& transitions = database[current], found = transitions.find(transition); if(found == transitions.end()) return false; auto const& next = found->second; set(next); return true; } /* Process so-called "automatic transitions" (ie: sequencing)

• /

bool process() { return process(get()); } /* A set of utility functions that may be helpful for displaying valid transitions to the user, etc...

• /

template <typename PushBackContainer> bool get_valid_transitions(State const& state, PushBackContainer& container) { container.clear(); auto const& found = database.find(state); if(found == database.end()) return false; auto const& transitions = found->second; if(transitions.size() == 0) return false; for(auto const& iterator : transitions) { auto const& transition = iterator.first; container.push_back(transition); } return true; } template <typename Container> bool get_valid_transitions(Container& container) { return get_valid_transitions(get(), container); } };

/* Example usage: a simple vending machine

• /

1. include <string>
2. include <vector>
3. include <iostream>

using namespace std; void print(string const& message) { cout << message << endl; } int main() { finite_state_machine<string> machine; 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"); machine.add("refunding", "ready"); machine.set("ready"); for(;;) { string 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") print("Refunding money..."); else if(state == "exit") break; else print("Internal error: unaccounted state '" + state + "'!"); /* Handle "automatic" transitions */ if(machine.process()) continue; vector<string> transitions; machine.get_valid_transitions(transitions); string options; for(auto const& transition : transitions) { if(!options.empty()) options += ", "; options += transition; } print("[" + state + "] Input the next transition (" + options + "): "); string transition; cout << " > "; cin >> transition; if(!machine.process(transition)) print( "Error: invalid transition!"); } } </lang>

Output:

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

Java

<lang java>import java.util.*;

public class FiniteStateMachine {

   private enum State {
       Ready(true, "Deposit", "Quit"),
       Waiting(true, "Select", "Refund"),
       Dispensing(true, "Remove"),
       Refunding(false, "Refunding"),
       Exiting(false, "Quiting");

       State(boolean exp, String... in) {
           inputs = Arrays.asList(in);
           explicit = exp;
       }

       State nextState(String input, State current) {
           if (inputs.contains(input)) {
               return map.getOrDefault(input, current);
           }
           return current;
       }

       final List<String> inputs;
       final static Map<String, State> map = new HashMap<>();
       final boolean explicit;

       static {
           map.put("Deposit", State.Waiting);
           map.put("Quit", State.Exiting);
           map.put("Select", State.Dispensing);
           map.put("Refund", State.Refunding);
           map.put("Remove", State.Ready);
           map.put("Refunding", State.Ready);
       }
   }

   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       State state = State.Ready;

       while (state != State.Exiting) {
           System.out.println(state.inputs);
           if (state.explicit){
               System.out.print("> ");
               state = state.nextState(sc.nextLine().trim(), state);
           } else {
               state = state.nextState(state.inputs.get(0), state);
           }
       }
   }

}</lang>

[Deposit, Quit]
> Deposit
[Select, Refund]
> Refund
[Refunding]
[Deposit, Quit]
> Deposit
[Select, Refund]
> Quit
[Select, Refund]
> Select
[Remove]
> Remove
[Deposit, Quit]
> Quit

Kotlin

<lang scala>// version 1.1.51

enum class State { READY, WAITING, EXIT, DISPENSE, REFUNDING }

fun fsm() {

   println("Please enter your option when prompted")
   println("(any characters after the first will be ignored)")
   var state = State.READY
   var trans: String

   while (true) {
       when (state) {
           State.READY -> {
               do {
                   print("\n(D)ispense or (Q)uit : ")
                   trans = readLine()!!.toLowerCase().take(1)
               }
               while (trans != "d" && trans != "q")
               state = if (trans == "d") State.WAITING else State.EXIT
           }

           State.WAITING -> {
               println("OK, put your money in the slot")
               do {
                   print("(S)elect product or choose a (R)efund : ")
                   trans = readLine()!!.toLowerCase().take(1)
               }
               while (trans != "s" && trans != "r")
               state = if (trans == "s") State.DISPENSE else State.REFUNDING
           }

           State.DISPENSE -> {
               do {
                   print("(R)emove product : ")
                   trans = readLine()!!.toLowerCase().take(1)
               }
               while (trans != "r")
               state = State.READY
           }

           State.REFUNDING -> {
               // no transitions defined
               println("OK, refunding your money")
               state = State.READY
           }

           State.EXIT -> {
               println("OK, quitting")
               return
           }
       }
   }

}

fun main(args: Array<String>) {

   fsm()

}</lang>

Sample input/output:

Please enter your option when prompted
(any characters after the first will be ignored)

(D)ispense or (Q)uit : d
OK, put your money in the slot
(S)elect product or choose a (R)efund : s
(R)emove product : r

(D)ispense or (Q)uit : d
OK, put your money in the slot
(S)elect product or choose a (R)efund : r
OK, refunding your money

(D)ispense or (Q)uit : q
OK, quitting

zkl

A lame FSM, we just convert text to a [hopefully valid] zkl program, compile and run it.

If we need true state to state hops, we could use tail recursion (another name for goto). <lang zkl>class FSM{ // our Finite State Machine

  var bank=0, item=Void;
  fcn deposit(coin){ bank=coin }
  fcn select(item){
     if(bank){ bank=0; self.item=item; } 
     else print("Depost coin, then select ") 
  }
  fcn take         { if(item) item=Void; else print("Select first "); }
  fcn refund       { coin:=bank; bank=0; return(coin) }

  // couple of wrappers to state changes
  fcn state{ println("Bank(%4d), Item(%s)".fmt(bank,item)) }
  fcn act(f){ print("%-10s-->".fmt(f.name)); f(); state(); }

}

Vault.add(FSM); // put class FSM where I can find it</lang> <lang zkl>fcn run(program){ // convert text to FSM instructions and run them

  program=program.replace("(",".fp(");  // deposit(10)-->deposit.fp(10)
  a,b,p := 0,0,Sink("class P(FSM){ state(); ");
  while(Void!=(b=program.find(";",a)))
     { p.write("act(",program[a,b-a],");"); a=b + 1; }
  program=p.write(program[a,*],"}").close();
  // println(program);  // WTH did I just do?
  Compiler.Compiler.compileText(program)();  // compile and run our little FSM

}</lang> <lang zkl>run("select(); take(); deposit(10); select(\"snickers\"); take();");</lang> The above is converted to: <lang zkl>class P(FSM){

  state(); 
  act(select.fp());
  act( take.fp());
  act( deposit.fp(10));
  act( select.fp("snickers"));
  act( take.fp());

}</lang> The .fp() is function application (ie deferred execution) so I can extract the function name and print it.

Output:

Bank(   0), Item(Void)
select    -->Depost coin, then select Bank(   0), Item(Void)
take      -->Select first Bank(   0), Item(Void)
deposit   -->Bank(  10), Item(Void)
select    -->Bank(   0), Item(snickers)
take      -->Bank(   0), Item(Void)