Explore FSM (Finite State Machine) applications

A Finite State Machine (FSM) is a mathematical model in computer science that can be used to represent and control the behavior of a system. It consists of a set of states and transition functions defined on those states. FSMs are widely used as state mechanisms in computer programs.

Finite state machine (FSM) application scenario

  • Applications in various automation systems: Such as traffic lights, turnstiles in subway stations, bank ATMs, etc. Through the definition of state and transition function, precise control of system behavior can be realized.

    Traffic light status flow diagram

    file

    The status flow diagram of the turnstile of the subway station

    file

    Bank ATM status flow diagram

    file

  • Applications in programming: For example, when writing compilers and interpreters, Finite State Machines (FSM) can be used to handle lexical analysis. For example: JSON.Parse

  • Application in Notion: You can use related concepts of Finite State Machine (FSM) to build various workflows, such as state transition diagrams, state transition tables, etc.

  • Application in the web: The familiar Promise is also a state machine with three states: pending and resolved. rejected.

    Promise state flow diagram

    file

    Login function flow chart

    file

There are countless examples of state machines like this, and even humans are an extremely complex state machine. Given a stimulus or a combination of multiple stimuli, it will trigger the transition from one state to another. It’s just that the complexity is so high that modern science is completely unable to decipher this state machine.

Finite state machine (FSM) realization principle

Specifically, FSM consists of the following parts:

  • Initial state: The initial state of the system.
  • State Collection: Indicates various states that the system may be in.
  • Transition function: Define the transition conditions and results of the system between different states.
  • Terminal state: The system can stop computing in a certain state.

The Finite State Machine (FSM) implementation is based on a state transition diagram. A state transition graph is a directed graph that represents the transition relationship between states in a finite state machine (FSM). In the state transition diagram, each state represents a certain state of the system, and each transition represents the conditions and results of the system transitioning from one state to another.

Implement a simple finite state machine (FSM)

implementation steps

  • When the state machine starts executing, it automatically enters the initial state.
  • Each state can define behavior events (actions) that occur when entering (onEnter) or exiting (onExit) the state, usually these behavior events will carry side effects (side effects).
  • Each state can define events that trigger transitions.
  • Transitions define how a state machine handles events when exiting one state and entering another.
  • Behavior events can be defined that can be triggered when a state transition occurs, which is generally used to express its side effects.

state transition diagram

file

function createMachine(stateMachineDefinition) {
  const machine = {
    value: stateMachineDefinition. initialState,
    performTransition(currentState, event) {
      const currentStateDefinition = stateMachineDefinition[currentState];
      const destinationTransition = currentStateDefinition. transitions[event];
      if (!destinationTransition) {
        return;
      }
      const destinationState = destinationTransition. target;
      const destinationStateDefinition =
        stateMachineDefinition[destinationState];

      destinationTransition. action();
      currentStateDefinition.actions.onExit();
      destinationStateDefinition.actions.onEnter();

      machine.value = destinationState;

      return machine. value;
    },
  };
  return machine;
}

const machine = createMachine({
  initialState: "off",
  off: {
    actions: {
      onEnter() {
        console.log("off: onEnter");
      },
      onExit() {
        console.log("off: onExit");
      },
    },
    transitions: {
      switch: {
        target: "on",
        action() {
          console.log('transition action for "switch" in "off" state');
        },
      },
    },
  },
  on: {
    actions: {
      onEnter() {
        console.log("on: onEnter");
      },
      onExit() {
        console.log("on: onExit");
      },
    },
    transitions: {
      switch: {
        target: "off",
        action() {
          console.log('transition action for "switch" in "on" state');
        },
      },
    },
  },
});

let state = machine. value;
console.log(`current state: ${state}`);
state = machine. performTransition(state, "switch");
console.log(`current state: ${state}`);
state = machine. performTransition(state, "switch");
console.log(`current state: ${state}`);

Application implementation of finite state machine (FSM)

In the case of many states, the states, events and transitions are concentrated in one state machine for unified management. In this way, you don’t need to write too many if-else, or case judgments. If you add states and events, it is also convenient for code maintenance and expansion.

text parser

Implementation ideas

  • Determine status and input
    Before writing an FSM, we need to determine our state and inputs. In this example, we will define three states: start state, number state and string state. We’ll also define four inputs: numbers, letters, quotes, and spaces.
  • Define the state machine class
    Now, we can write the code to implement our FSM. We need to define a state machine class that will take input and transition states according to transition rules. This class should contain the following properties:
    • currentState: current state.
    • states: list of states.
    • transitions: list of transitions.
      It should also contain the following methods:
    • transition: This method accepts an input parameter input, and performs the corresponding state transition according to the current state and the input parameter.
  • Define transfer rules
    We also need to define transition rules between states. For this, we’ll use transition lists, which contain mappings and inputs between states. Transition rules should consider the current state and inputs and determine the next state based on them. An exception should be thrown if the current state and input do not have a matching transition rule.
  • Parse text
    Now, we can use the state machine to parse the text. We need to split the text into words and feed each word as input to the state machine. After all input has been processed, we can get the parsed token by calling the getInputType method.

sample code

const STATES = {
  START: "start",
  NUMBER: "number",
  STRING: "string",
};

const INPUTS = {
  NUMBER: "number",
  LETTER: "letter",
  SPACE: "space",
  QUOTE: "quote",
};

const TRANSITIONS = [
  {
    currentState: STATES. START,
    input: INPUTS. NUMBER,
    nextState: STATES. NUMBER,
  },
  {
    currentState: STATES. START,
    input: INPUTS.LETTER,
    nextState: STATES. STRING,
  },
  { currentState: STATES.START, input: INPUTS.SPACE, nextState: STATES.START },
  { currentState: STATES.START, input: INPUTS.QUOTE, nextState: STATES.STRING },
  {
    currentState: STATES. NUMBER,
    input: INPUTS. NUMBER,
    nextState: STATES. NUMBER,
  },
  { currentState: STATES.NUMBER, input: INPUTS.SPACE, nextState: STATES.START },
  {
    currentState: STATES. STRING,
    input: INPUTS.LETTER,
    nextState: STATES. STRING,
  },
  { currentState: STATES. STRING, input: INPUTS. SPACE, nextState: STATES. START },
  { currentState: STATES.STRING, input: INPUTS.QUOTE, nextState: STATES.START },
];

class TextParse {
  constructor() {
    this.currentState = STATES.START;
    this.buffer = "";
    this.type;
  }

  performTransition(input) {
    const transition = TRANSITIONS. find(
      (t) => t.currentState === this.currentState & amp; & amp; t.input === input.type
    );
    if (!transition)
      throw new Error(
        `Invalid input "${input.value}" for state "${this.currentState}"`
      );

    this.currentState = transition.nextState;

    if (this. currentState === STATES. START) {
      const token = this.buffer;
      const type = this.type;
      this.buffer = "";
      this.type = "";
      return {
        type,
        value: token,
      };
    } else {
      this.buffer += input.value;
      this.type = input.type;
    }
  }
}

function textParse(input) {
  const textParse = new TextParse();
  const tokens = [];

  for (let i = 0; i < input. length; i ++ ) {
    const char = input[i];

    try {
      const token = textParse. performTransition({
        type: getInputType(char),
        value: char,
      });

      if (token) {
        tokens. push(token);
      }
    } catch (e) {
      console.error(e.message);
      return null;
    }
  }

    const lastToken = textParse. performTransition({ type: INPUTS. SPACE });

  if (lastToken) {
    tokens.push(lastToken);
  }

  return tokens;
}

function getInputType(char) {
  if (/[0-9]/.test(char)) {
    return INPUTS. NUMBER;
  } else if (/[a-zA-Z]/.test(char)) {
    return INPUTS.LETTER;
  } else if (/[\s\
\t\r]/.test(char)) {
    return INPUTS. SPACE;
  } else if (char === '"') {
    return INPUTS.QUOTE;
  } else {
    throw new Error(`Unknown input type for "${char}"`);
  }
}

// Example usage:
console.log(textParse('123 abc "def ghi" 456'));
//[
// { type: 'number', value: '123' },
// { type: 'letter', value: 'abc' },
// { type: 'letter', value: '"def' },
// { type: 'letter', value: 'ghi' },
// { type: '', value: '' },
// { type: 'number', value: '456' }
// ]

sample code

web application

Use Finite State Machine (FSM) combined with React to build web applications, not limited to identity authentication, login, step form, there are quite a lot of web applications in
The practice of finite state machine (FSM), the following mainly describes the application of the state transition of pulling data from the finite state machine (FSM) on the server side

  • State transition diagram

    file

  • States, Transitions

const states = {
  INITIAL: "idle",
  LOADING: "loading",
  SUCCESS: "success",
  FAILURE: "failure",
};

const transitions = {
  [states. INITIAL]: {
    fetch: () => /* Returns states. LOADING */,
  },

  [states.LOADING]: {},

  [states. SUCCESS]: {
    reload: () => /* Returns states. LOADING */,
    clear: () => /* Returns states. INITIAL */,
  },

  [states.FAILURE]: {
    retry: () => /* Returns states. LOADING */,
    clear: () => /* Returns states. INITIAL */,
  },
}

sample code

Summary

There are not many explorations combined with front-end applications, which can be discussed as the second content. Students who are interested can try the application exploration of Finite State Machine (FSM) on the web, and The application of >Xstate library (a functional library encapsulated by FSM), and the knowledge of differentiation from state management library. Here is a reminder that the state management library (Redux) and Xstate are not mutually exclusive. Xstate focuses on how to design state, state management The library is concerned with how to manage state. In fact, State Machines can be used with almost any state management tool that is not opinionated. I encourage you to explore various approaches to determine what works best for you, your team, and your application.

The knowledge points of the article match the official knowledge files, and you can further learn relevant knowledge Java skill treeHome pageOverview 126971 people are studying systematically