FSM data structure design

Question

I want to write an FSM that starts with a wait state and moves from one state to another based on some kind of event. I am not familiar with FSM coding, and Google did not help. Appreciate if someone can post a C data structure that can be used for the same.

Thank syuga2012

Answer 1

In the past, we implemented the final machine for Telcos and always used an array of structures pre-populated as:

/* States */ #define ST_ANY 0 #define ST_START 1 : : : : : /* Events */ #define EV_INIT 0 #define EV_ERROR 1 : : : : : /* Rule functions */ int initialize(void) { /* Initialize FSM here */ return ST_INIT_DONE } : : : : : /* Structures for transition rules */ typedef struct { int state; int event; (int)(*fn)(); } rule; rule ruleset[] = { {ST_START, EV_INIT, initialize}, : : : : : {ST_ANY, EV_ERROR, error}, {ST_ANY, EV_ANY, fatal_fsm_error} }; 

I may have a function pointer fn declared invalid, as it is from memory. Basically, the state machine looked for an array for the corresponding state and event and called a function that did what was supposed to be done, and then returned a new state.

Specific states were placed first, and ST_ANY records continued because the priority of the rules depended on their position in the array. The first rule found was used.

In addition, I remember that we had an array of indexes to the first rule for each state in order to speed up the search (all rules with the same starting state were grouped).

Also keep in mind that this was pure C - maybe the best way to do this is with C ++.

Answer 2

A state machine consists of a finite number of discrete states (I know pedantic, but still), which can usually be represented as integer values. In c or C ++, using an enumeration is very common.

The device responds to a finite number of inputs, which can often be represented by another integer variable. In more complex cases, you can use a structure to represent input status.

Each combination of internal state and external input will cause the device to:

• possible transition to another state
• possibly generating some output

A simple case of c might look like this:

 enum state_val { IDLE_STATE, SOME_STATE, ... STOP_STATE } //... state_val state = IDLE_STATE while (state != STOP_STATE){ int input = GetInput(); switch (state) { case IDLE_STATE: switch (input) { case 0: case 3: // note the fall-though here to handle multiple states write(input); // no change of state break; case 1: state = SOME_STATE; break case 2: // ... }; break; case SOME_STATE: switch (input) { case 7: // ... }; break; //... }; }; // handle final output, clean up, whatever 

although it is difficult to read and more easily broken down into several functions, for example:

  while (state != STOP_STATE){ int input = GetInput(); switch (state) { case IDLE_STATE: state = DoIdleState(input); break; // .. }; }; 

with the complexities of each state contained in its own function.

As m3rLinEz says , you can navigate in an array for quick indexing. You can also hold the function pointer in an array to handle the phase of the action efficiently. This is especially useful for the automatic generation of large and complex state machines.

Answer 3

The answers here seem very complicated (but accurate, nonetheless.) So, here are my thoughts.

First, I like the dmckee (online) definition of FSM and how they apply to programming.

A state machine consists of a finite number of discrete states (I know pedantic, but still), which are usually represented as integer values. In c or C ++ using enumeration is very common.

The machine responds to a finite number of inputs, which can often be represented by another integer meaningful variable. In more complex cases, you can use a structure to represent the input state.

Each combination of internal state and external input will call in:

• possible transition to another state
• possibly generating some output

So you have a program. It has states, and their finite number. (“light bulb is bright” or “light bulb dims” or “light bulb is off.” 3 states are final.) Your program can only be in one state at a time.

So, say you want your program to change states. Usually you need something to happen to cause a state change. In this example, how about entering user input to determine the state — say, a keystroke.

You may need this logic. When the user presses a key:

• If the light is off, turn the light off.
• If the light “dims”, make the light “bright”.
• If the lamp is bright, turn the lamp off.

Obviously, instead of "replacing the light bulb", you can "change the color of the text" or whatever you do in the program. Before you begin, you want to define your states.

So, let's look at some pseudo-code C:

 /* We have 3 states. We can use constants to represent those states */ #define BULB_OFF 0 #define BULB_DIM 1 #define BULB_BRIGHT 2 /* And now we set the default state */ int currentState = BULB_OFF; /* now we want to wait for the user input. While we're waiting, we are "idle" */ while(1) { waitForUserKeystroke(); /* Waiting for something to happen... */ /* Okay, the user has pressed a key. Now for our state machine */ switch(currentState) { case BULB_OFF: currentState = BULB_DIM; break; case BULB_DIM: currentState = BULB_BRIGHT; doCoolBulbStuff(); break; case BULB_BRIGHT: currentState = BULB_OFF; break; } } 

And voila. A simple program that changes state.

This code executes only a small part of the switch , depending on the current state. He then updates this state. How FSM works.

Now here are a few things you can do:

• Obviously, this program simply modifies the currentState variable. You want your code to do something more interesting when the state changes. The doCoolBulbStuff() function could, I don’t know, actually draw a light bulb on the screen. Or something.

• This code only searches for keystrokes. But your FSM (and therefore your switch statement) can choose a state based on what the user enters (for example, "O" means "go off", and not just go to what's in the sequence.)

Part of your question asked the data structure.

One person suggested using enum to track conditions. This is a good #defines alternative that I used in my example. People also offered arrays - and these arrays track transitions between states. It is also a thin structure to use.

Given the above, you can use any structure (something tree-like, an array, whatever) to track individual states and determine what to do in each state (therefore, some of the suggestions for using "function pointers" - have a state map for a function pointer that indicates what to do in this state.)

Hope this helps!

Answer 4

See Wikipedia for a formal definition. You need to define your set of states S, your input alphabet, and Sigma; and your transition function .delta. The simplest representation is that S be the set of integers 0, 1, 2, ..., N-1, where N is the number of states, and for & Sigma; is the set of integers 0, 1, 2, ..., M-1, where M is the number of inputs, and then? is simply a large matrix of N by M. Finally, you can save a set of receiving states by storing an array of N bits, where the i-th bit is 1 if the i-th state is a receiving state, or 0 if it is not a receiving state.

For example, here is the FSM in Figure 3 of the Wikipedia article:

 #define NSTATES 2 #define NINPUTS 2 const int transition_function[NSTATES][NINPUTS] = {{1, 0}, {0, 1}}; const int is_accepting_state[NSTATES] = {1, 0}; int main(void) { int current_state = 0; // initial state while(has_more_input()) { // advance to next state based on input int input = get_next_input(); current_state = transition_function[current_state][input]; } int accepted = is_accepting_state[current_state]; // do stuff } 

Answer 5

Basically, you can use the "if" conditional and variable to store the current state of FSM.

For example (just a concept):

 int state = 0; while((ch = getch()) != 'q'){ if(state == 0) if(ch == '0') state = 1; else if(ch == '1') state = 0; else if(state == 1) if(ch == '0') state = 2; else if(ch == '1') state = 0; else if(state == 2) { printf("detected two 0s\n"); break; } } 

For a more complex implementation, you can consider transitioning the state of the storage in a two-dimensional array:

 int t[][] = {{1,0},{2,0},{2,2}}; int state = 0; while((ch = getch()) != 'q'){ state = t[state][ch - '0']; if(state == 2){ ... } } 

Answer 6

Several AT&T guys, now at Google, have created one of the best FSM libraries available for general use. Check it out here, it's called OpenFST .

It's fast, efficient, and they have created a very clear set of operations that you can perform in FSM to do things like minimize them or define them to make them even more useful for real problems.

Answer 7

If by FSM you mean a state machine, and you like it simply, use the enumerations to name your states and switch between them.

Otherwise, use functors. you can see fancy definition in stl or boost docs.

These are more or less objects having a method, for example. called run (), which does everything that needs to be done in this state, with the advantage that every state has a scope.