A bit about the state machine (FSM SMR DFSM)

Finite state machine （Finite State Machine）

Finite state machine （ English ：finite-state machine, abbreviation ：FSM） Also known as finite state automata （ English ：finite-state automaton, abbreviation ：FSA）, State machine for short , It is a mathematical calculation model that represents a finite number of States and the transfer and action between these states .- Wikipedia

• Elements of a finite state machine
  • state ： States are finite , Any moment , Only in one state
  • Conditions ： Used to trigger the state transition action “ event ”, The conditions are met （ Input ） The corresponding action will be triggered
  • action ： When the conditions are met , The act of performing a state transition
  • transformation ： Transition from one state to another , The transition is usually done by the state transition function

Let's look at a classic example of a finite state machine ： Rotary gate （ In these days, coins are basically not used for gate machines ）

Rotary gate

If you use a state diagram, it looks like this ：

State transition diagram

• state ： The rotary gate has only two states ： Lock and unlock
• Conditions 、 action 、 transformation ： Gate The initial state It's locking （Locked） Of , When tourists place coins （Coin） When entering the gate , The gate will be switched to unlock （Un-locked） state , When the tourists push through the gate , The state of the gate will be changed to locked （Locked）.
  • When the gate is unlocked （Un-locked） In the state of , It's no use putting coins in repeatedly , The state will not change , Empathy , Locked state , Over and over again Push Revolving doors are useless , The gate state will not change , Tourists can't get through .

The state transition table is shown in the following figure ：

State transition table

Go To realize the FSM

be based on Go Language , It can realize the function of rotary gate FSM as follows ,StateTransitionTable This is the state transition table ：

package main

import (
	"bufio"
	"fmt"
	"log"
	"os"
	"strings"
)

const (
	Locked = iota
	Unlocked
)

const (
	InputCoin = "coin"
	InputPush = "push"
)

type State uint32

type StateTransitionTableDef struct {
	State State
	Input string
}

// Action
type TransitionFunc func(state *State)

var StateTransitionTable = map[StateTransitionTableDef]TransitionFunc{
	{Locked, InputCoin}: func(state *State) {
		fmt.Println("Unlocks the turnstile so that the customer can push through.")
		*state = Unlocked
	},
	{Locked, InputPush}: func(state *State) {
		fmt.Println("The turnstile has been locked.")
	},
	{Unlocked, InputCoin}: func(state *State) {
		fmt.Println("The turnstile has been unlocked.")
	},
	{Unlocked, InputPush}: func(state *State) {
		fmt.Println("When the customer has pushed through, locks the turnstile.")
		*state = Locked
	},
}

type TurnStile struct {
	State State
}

func (t *TurnStile) ExecuteAction(action string) {
	stateActionTupple := StateTransitionTableDef{
		t.State,
		strings.TrimSpace(action),
	}

	if transFunc := StateTransitionTable[stateActionTupple]; transFunc == nil {
		fmt.Println("Unknown action, please try again!")
	} else {
		transFunc(&t.State)
	}
}

func main() {
	turnstileFSM := &TurnStile{
		State: Locked, // Initial State
	}

	prompt(turnstileFSM.State)
	reader := bufio.NewReader(os.Stdin)

	for {
		action, err := reader.ReadString('\n')
		if err != nil {
			log.Fatalln(err)
		}

		turnstileFSM.ExecuteAction(action)
	}
}

func prompt(s State) {
	m := map[State]string{
		Locked:   "Locked",
		Unlocked: "Unlocked",
	}
	fmt.Printf("current state is: [%s], please input action: [coin | push]: \n", m[s])
}

FSM application - Lexical analysis

FSM A typical application is for the compiler front end -> Lexical analyzer （Lexer） Lexical analysis of （tokenize）. For example, the following relational expression statement tokenize On ：

• blogAge > 3

our Lexer When scanning relational expressions, you need to recognize blogAge For identifier （Identifier）,> For the comparison operator （Greater）,3 Is a numeric literal （NumericLiteral）, The corresponding lexical rules are as follows ：

• identifier （Identifier）： The first character needs to be a letter , Other characters can be numbers or letters or underscores
• Comparison operator （Greater）：>
• Number literal quantity （NumericLiteral）： It's all made up of numbers

Corresponding FSM The simplified state diagram is as follows ：

Relational expression lexical analysis state diagram

Copy state machine （Replicated State Machine）

In the field of Distributed Systems , The state machine is used to ensure the consistency of node states , Distributed system consistency algorithm is based on replication state machine （Replicated State Machine） Bring up the .

Replication state machine architecture

every last Server Every node has a state machine , The input source of this state machine is a log that stores the command sequence , For the same command, enter , Each node state machine （ Determine finite automata DFA,Deterministic Finite Automata） The output of is certain 、 same .

Reference resources

• Copy state machine
• Finite-state machine
• Use Golang Implementation state machine