理解有限状态机

什么是有限状态机?

有限状态机也叫状态机,是一种编程思想或者说是编程范式。在有限状态机中:

  • 每个状态都是一个机器
    • 在每个机器中,可以做计算、存储或输出等等…
    • 所有的机器接受的输入是一致的
    • 状态机的每一个机器本身没有状态,如果我们用函数表示的话,它应该是纯函数(即不依赖于外部环境,无副作用)
  • 每一个机器都知道下一个状态
    • 每个机器都有确定的下一个状态(Moore)
    • 每个机器根据输入决定下一个状态(Melay)

JavaScript中的有限状态机实现(Melay)

  • 每个函数是一个状态,函数参数就是输入

    1
    2
    3
    4
    function state(input) {
    // do something here
    return next; // 返回值作为下一个状态
    }
  • 调用状态机

    1
    2
    3
    while(input) {
    state = state(input); // 把状态机的返回值作为下一个状态
    }

实例:使用状态机匹配字符串”abcdef”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
function match(string) {
let state = start; // 初始状态为start
// 遍历整个字符串
for(let c of string) {
state = state(c);
}
return state === end; // 判断最后状态是否是end
}

// 开始状态
function start(c) {
if(c === 'a') { // 如果找到字符'a'则进入foundA状态
return foundA;
}else {
return start;
}
}

// 结束状态
function end() {
return end;
}

function foundA(c) {
if(c === 'b') { // 如果找到字符'b'则进入foundB状态
return foundB;
}else {
return start(c);
}
}

function foundB(c) {
if(c === 'c') { // 如果找到字符'c'则进入foundC状态
return foundC;
}else {
return start(c);
}
}

function foundC(c) {
if(c === 'd') { // 如果找到字符'd'则进入foundD状态
return foundD;
}else {
return start(c);
}
}

function foundD(c) {
if(c === 'e') { // 如果找到字符'a'则进入foundE状态
return foundE;
}else {
return start(c);
}
}

function foundE(c) {
if(c === 'f') { // 如果找到字符'f'则进入end状态
return end;
}else {
return start(c);
}
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2019-2021 musi

请我喝杯咖啡吧~

支付宝
微信