有限状态机(英语:finite-state machine,缩写:FSM)又称有限状态自动机(英语:finite-state automaton,缩写:FSA),简称状态机,是表示有限个状态以及在这些状态之间的转移和动作等行为的数学计算模型。- 维基百科
让我们来看下有限状态机的经典例子:旋转闸机(这年代闸机基本不用硬币了😂)
使用状态图表示的话就是下面这样子:
用状态转换表表示如下图:
基于 Go 语言,可实现旋转门闸机的 FSM 如下,StateTransitionTable 即为状态转换表:
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 很典型的一个应用就是用于编译器前端->词法分析器(Lexer)的词法分析上(tokenize)。比如如下关系表达式语句的 tokenize 上:
我们的 Lexer 扫描关系表达式时需要识别到 blogAge 为标识符(Identifier),> 为比较操作符(Greater),3 为数字字面量(NumericLiteral),对应的词法规则如下:
对应的 FSM 简化版状态图如下:
在分布式系统领域,状态机被用于保证节点状态的一致性,分布式系统一致性算法是基于复制状态机(Replicated State Machine)提出来的。
每一个 Server 节点都会有一个状态机,这个状态机的输入来源为一份储存着命令序列的日志,对于相同的命令输入,每个节点状态机(确定有限自动机 DFA,Deterministic Finite Automata)的输出是确定的、相同的。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。