Finite state machine: Difference between revisions
(Made draft) |
(→{{header|C++}}: Simplified example, minor variable renaming (for clarity)) |
||
Line 21: | Line 21: | ||
database; |
database; |
||
State |
State |
||
current; |
|||
public: |
public: |
||
finite_state_machine() |
finite_state_machine() |
||
Line 30: | Line 30: | ||
set(State const& state) |
set(State const& state) |
||
{ |
{ |
||
current = state; |
|||
} |
} |
||
State |
State |
||
get() const |
get() const |
||
{ |
{ |
||
return |
return current; |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
} |
} |
||
void |
void |
||
Line 54: | Line 59: | ||
{ |
{ |
||
auto const& |
auto const& |
||
transitions = database[ |
transitions = database[current], |
||
found = transitions.find(transition); |
found = transitions.find(transition); |
||
if(found == transitions.end()) |
if(found == transitions.end()) |
||
return false; |
return false; |
||
auto const& |
auto const& |
||
state = found->second; |
|||
set( |
set(state); |
||
return true; |
return true; |
||
} |
} |
||
Line 80: | Line 85: | ||
container.clear(); |
container.clear(); |
||
auto const& |
auto const& |
||
found = database.find(state); |
|||
if( |
if(found == database.end()) |
||
return false; |
return false; |
||
auto const& |
auto const& |
||
transitions = |
transitions = found->second; |
||
if(transitions.size() == 0) |
if(transitions.size() == 0) |
||
return false; |
return false; |
||
for(auto const& |
for(auto const& iterator : transitions) |
||
{ |
|||
⚫ | |||
auto const& |
|||
transition = iterator.first; |
|||
⚫ | |||
} |
|||
return true; |
return true; |
||
} |
} |
||
Line 96: | Line 105: | ||
{ |
{ |
||
return get_valid_transitions(get(), container); |
return get_valid_transitions(get(), container); |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
} |
} |
||
}; |
}; |
||
Line 126: | Line 130: | ||
machine.add("ready", "quit", "exit"); |
machine.add("ready", "quit", "exit"); |
||
machine.add("ready", "deposit", "waiting"); |
machine.add("ready", "deposit", "waiting"); |
||
machine.add("waiting", " |
machine.add("waiting", "select", "dispense"); |
||
machine.add("waiting", "refund", "refunding"); |
machine.add("waiting", "refund", "refunding"); |
||
machine.add("dispense", "remove", "ready"); |
machine.add("dispense", "remove", "ready"); |
||
machine.add("dispense", "stuck", "refunding"); |
|||
machine.add("refunding", "ready"); |
machine.add("refunding", "ready"); |
||
machine.set("ready"); |
machine.set("ready"); |
||
Line 139: | Line 142: | ||
print("Please deposit coins."); |
print("Please deposit coins."); |
||
else if(state == "waiting") |
else if(state == "waiting") |
||
print("Please |
print("Please select a product."); |
||
else if(state == "dispense") |
else if(state == "dispense") |
||
print("Dispensed...please remove product from tray."); |
print("Dispensed...please remove product from tray."); |
||
Line 178: | Line 181: | ||
[ready] Enter next transition (deposit, quit): |
[ready] Enter next transition (deposit, quit): |
||
> deposit |
> deposit |
||
Please |
Please select a product. |
||
[waiting] Enter next transition (refund, |
[waiting] Enter next transition (refund, select): |
||
> selection |
|||
Dispensed...please remove product from tray. |
|||
[dispense] Enter next transition (remove, stuck): |
|||
> stuck |
|||
Refunding money... |
|||
Please deposit coins. |
|||
[ready] Enter next transition (deposit, quit): |
|||
> deposit |
|||
Please make a selection! |
|||
[waiting] Enter next transition (refund, selection): |
|||
> refund |
> refund |
||
Refunding money... |
Refunding money... |
||
Line 195: | Line 188: | ||
[ready] Enter next transition (deposit, quit): |
[ready] Enter next transition (deposit, quit): |
||
> deposit |
> deposit |
||
Please |
Please select a product. |
||
[waiting] Enter next transition (refund, |
[waiting] Enter next transition (refund, select): |
||
> |
> select |
||
Dispensed...please remove product from tray. |
Dispensed...please remove product from tray. |
||
[dispense] Enter next transition (remove |
[dispense] Enter next transition (remove): |
||
> remove |
> remove |
||
Please deposit coins. |
Please deposit coins. |
Revision as of 19:35, 24 August 2017
A Finite state machine (FSM) is computational abstraction which maps a finite number of states to other states in the same set via transitions. Transitions can either be explicit or implicit (ie: "automatic"/sequenced). An FSM can only be in one state at any given moment.
- Task
Implement a simple finite state machine which handles both explicit and implicit transitions. Then demonstrate an example which models some real-world process (such as a vending machine).
- See also
- Computers Without Memory (Finite State Automata), A Computerphile Video.
C++
<lang C>
- include <map>
template <typename State, typename Transition = State> class finite_state_machine { protected: std::map<State, std::map<Transition, State>> database; State current; 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& state = found->second; set(state); 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 Container> bool get_valid_transitions(State const& state, Container& 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
- /
- include <string>
- include <vector>
- 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; /* Handle "automatic" transitions */ if(machine.process()) continue; vector<string> transitions; machine.get_valid_transitions(transitions); string options; for(auto const& text : transitions) { if(!options.empty()) options += ", "; options += text; } print("[" + machine.get() + "] Enter next transition (" + options + "): "); string transition; cout << " > "; cin >> transition; if(!machine.process(transition)) print( "Error: invalid transition!"); } } </lang>
- Output:
Please deposit coins. [ready] Enter next transition (deposit, quit): > deposit Please select a product. [waiting] Enter next transition (refund, select): > refund Refunding money... Please deposit coins. [ready] Enter next transition (deposit, quit): > deposit Please select a product. [waiting] Enter next transition (refund, select): > select Dispensed...please remove product from tray. [dispense] Enter next transition (remove): > remove Please deposit coins. [ready] Enter next transition (deposit, quit): > quit