证明与计算(7): 有限状态机(Finite State Machine)

 什么是有限状态机(Finite State Machine)? 什么是确定性有限状态机(deterministic finite automaton, DFA )? 什么是非确定性有限状态机(nondeterministic finite automaton, NDFA, NFA)? [1] [wiki-en: Finite state machine](https://en.wikipedia.org/wiki/Finite-state_machine) [2] [wiki-zh-cn: Finite state machine](https://zh.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E7%8A%B6%E6%80%81%E6%9C%BA) [3] [brilliant: finite-state-machines](https://brilliant.org/wiki/finite-state-machines/) 上面的这3个地址里的介绍已经写的很好了。第3个地址的是一个简约的FSM介绍，比较实用，而且基本上能让你区分清楚DFA和NFA。但是本文还是尝试比较清楚的梳理清楚它们之间的来龙去脉。 ## 0x02 Deterministic finite automaton, DFA 简单说，DFA包含的是5个重要的部分： * $Q$ = 一个有限状态集合 * $\Sigma$ = 一个有限的非空输入字符集 * $\delta$ = 一系列的变换函数 * $q_0$ = 开始状态 * $FF$ = 接受状态集合 在有限状态机的图里面，有几个约定： * 一个圆圈表示非接受状态 * 两个圆圈表示接受状态 * 箭头表示状态转移 * 箭头上的字符表示输入字符 例如下面两个DFA的图示： DFA图1（[3])： https://upload.wikimedia.org/wikipedia/commons/thumb/9/9d/DFAexample.svg/700px-DFAexample.svg.png  DFA图2: https://swtch.com/~rsc/regexp/fig0.png  DFA的特征是，**每个状态，输入一个新字符，都有一个唯一的输出状态**。 例如，DFA图1和图2的每个$S_i$在遇到0或者1时输出的状态时唯一的。 在DFA图1中，可以详细看下买个参数是什么（[3])： * Q = $\{s_1, s_2\}$ * $\Sigma$ = {0,1} * $q_0$ = $s_1$ ​* F = {s_1} 特别的，我们看下转换函数集合，实际上可以用一个表格来表示（[3])： |当前状态|输入状态｜输出状态｜ |:--|:--|:--| |s1|1|s1| |s1|0|s2| |s2|1|s2| |s2|0|s1| ## 0x03 Nondeterministic finite automaton, NDFA, NFA 那么，NFA和DFA的区别是什么呢？下面两个NFA的图示： NFA图1: https:/https://img.qb5200.com/download-x/ds055uzetaobb.cloudfront.net/brioche/uploads/zgipUhyx8b-ndfa2.png?width=2400  NFA图2: https://swtch.com/~rsc/regexp/fig2.png  NFA的特征是，和DFA相比： 1. **每个状态，输入一个新字符，可能有多个不同的输出状态**。 2. **每个状态，可以接受空输入字符，用符号$\epsilon$表示**。 例如NFA图2里，s2接受输入字符b之后，可能是s1，也可能是s3。而在NFA图1里，初始字符可以接受空输入$\epsilon$，不消耗任何字符，转换为b或者e状态，并且还是个多路分支。 ## 0x04 Regular Expression [4] [wiki-en: Regex Expression](https://en.wikipedia.org/wiki/Regular_expression) [5] [wiki-zh-cn: Regex Expression](https://zh.wikipedia.org/wiki/%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F) [6] [Regular Expression Matching Can Be Simple And Fast](https://swtch.com/~rsc/regexp/regexp1.html) 正则表达式和DFA/NFA的关系是什么？我们先看看正则表达式本身。[4]和[5]的wiki里列出了很多正则的表达式符号，但是不如文章[6]简洁实用。 首先，任何通配符都必须有逃逸字符。正则表达式的逃逸字符是`\`，例如`\+`不表示通配符，而表示的是匹配`+`字符。 其次，实际上根据[6]，正则表达式最重要的通配符就是三个： * `e*` 表示0个或多个e * `e+` 表示1个或多个e * `e?` 表示0个或1个e 最后，根据[6]，正则表达式最基础的组合方式也就是三个： * `e1e2` 表示e1和e2的拼接 * `e1|e2` 表示e1或者e2 * `e1(e2e3)` 表示分组，括号里的优先级更高，和括号在四则运算表达式里的作用一样 这里特别提一下，如果上述里的e替换成了一个集合，那么`e*`会变成`{e1,e2}*`，这个叫做集合`{e1,e2}`的**克林闭包(Kleene closure, Kleene operator, Kleene star)**，下面的两个wiki介绍了它们的定义： [7] [wiki-en: Kleene closure](https://en.wikipedia.org/wiki/Kleene_star) [8] [wiki-zh-cn: 克林闭包](https://zh.wikipedia.org/wiki/%E5%85%8B%E8%8E%B1%E5%B0%BC%E6%98%9F%E5%8F%B7) 它的定义是递归方式的，令目标集合是V： * $V_{0}=\{\epsilon \}\$ * $V_1$ = V * $V_{i+1} = { wv : w ∈ V_i and v ∈ V } for each i > 0.$ 从而，V的克林闭包如下：  一个克林闭包的例子如下： {"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}. 从而，也可以定义克林正闭包(Kleene Plus):  一个克林正闭包的例子如下： {"a", "b", "c"}+ = { "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab", ...}. ## 0x05 Regular Expression 2 NFA 根据文章[4]，正则表达式的三个重要的通配符，可以通过如下的方式转换为对应的NFA，这里用[s]表示非接受状态，用[[s]] 表示接受状态： 表达式 `e`： ``` [s]--e--> ``` 表达式 `e1e2`： ``` [s]--e1-->[]--e2--> ``` 表达式 `e1|e2`： ``` --e1--> / [s] \ --e2--> ``` 表达式 `e?`，可以看到它等价于`e|$\epsilon$` ``` --e--> / [s] \ ------> ``` 表达式 `e*`，上半部分本来有输出箭头，但是既然它能立刻绕回去上一个状态（转N圈），就可以直接从下半部分的箭头出去 ``` --e-- / | [s] <--- \ ------> ``` 表达式 `e+`，我们可以看成是它的等价形式`ee*`，那么就是 ``` --e-- / | --e-->[s] <--- \ ------> ``` 但是我们可以简化下，把分支上半部分（遇到一个输入e，合并到左侧，因为左侧也是表示**输入e然后到状态[]**： ``` ---- ↓ | --e-->[s] \ ------> ``` 有了这些基本的转换规则，就可以把正则表达式转换为NFA，这几个图最好自己动手画一下，不动手可能还是没有实际的感觉。 ## 0x06 NFA 2 DFA 由于NFA的定义是DFA的超集，一个DFA可以直接看做是一个NFA。 那么，NFA是否可以转化为DFA呢？ 当然可以，很显然，对比DFA和NFA的区别，有两点要做到： * 需要消灭所有的空输入 $\epsilon$ * 需要合并那些同一个字符的多路分支为一个分支，为了这点，转换后的DFA的每个状态是由NFA的状态构成的集合，例如{a,b}作为一个整体构成转换后的DFA的一个状态 [9] [nfa-2-dfa example](https://www.cs.odu.edu/~toida/nerzic/390teched/regular/fa/nfa-2-dfa.html) 我们先看一个实际的例子[9]，直接手工体验下这个转换过程： DFA图3: https://www.cs.odu.edu/~toida/nerzic/390teched/regular/fa/figures/nfa-dfa1.jpg  目标是找到对应的NFA的5个部分，有2个是现成的，剩下3个： * 状态集合Q * x 输入字符集合E，这个保持不变 * x 初始状态q0，这个保持不变 * 转移函数集合$\delta$ * 输出状态集合F 第1轮，考虑DFA里的Q第1个元素{} 1. 初始化Q={} 2. NFA的初始状态是0，我们把`{0}`这个集合，作为一个元素，加入Q，从而： * Q={ {0} } 3. NFA里，下一个输入a后可以是状态1，也可以是状态2，也就是$\delta$(0, a) = {1, 2}。因此，对应的DFA里： * Q={ {0},{1,2} } * $\delta$({0}, a) = {1, 2} 4. NFA里，$\delta$(0, b) = {}，因此空集被加入到DFA的Q里： * Q = { {},{0},{1,2} } * $\delta$({0}, a) = {1, 2}, $\delta$({0}, b) = {} 第2轮，考虑DFA里Q的第2个元素{1,2} 1. 此时{1,2}在DFA的Q里，考虑从{1,2}这个元素出发会到哪里 2. NFA里，$\delta$(1, a) = {1, 2}, $\delta$(2, a) = {}，从而 * DFA里新增 $\delta$({1,2}, a) = {1,2}, Q 则保持不动： * Q = { {},{0},{1,2} } * $\delta$({0}, a) = {1, 2}, $\delta$({0}, b) = {}， $\delta$({1,2}, a) = {1,2} 3. NFA里$\delta$(1, b) = {}, $\delta$(2, b) = {1,3}，从而 * DFA里新增 $\delta$({1,2}, b) = {1,3}, Q 新增{1,3}: * Q = { {},{0},{1,2},{1,3} } * $\delta$({0}, a) = {1, 2}, $\delta$({0}, b) = {}， $\delta$({1,2}, a) = {1,2}, $\delta$({1,2}, b) = {1,3} 第3轮，考虑DFA里Q的新增元素{1,3} 1. NFA里，$\delta$(1, a) = {1, 2}, $\delta$(3, a) = {1, 2} * DFA新增$\delta$({1,3}, a) = {1, 2}, Q 则保持不动 * Q = { {},{0},{1,2},{1,3} } * $\delta$({0}, a) = {1, 2}, $\delta$({0}, b) = {}， $\delta$({1,2}, a) = {1,2}, $\delta$({1,2}, b) = {1,3}, $\delta$({1,3}, a) = {1, 2} 2. NFA里，$\delta$(1, b) = {}, $\delta$(3, b) = {} * DFA新增$\delta$({1,3}, b) = {}, Q 则保持不动 * Q = { {},{0},{1,2},{1,3} } * $\delta$({0}, a) = {1, 2}, $\delta$({0}, b) = {}， $\delta$({1,2}, a) = {1,2}, $\delta$({1,2}, b) = {1,3}, $\delta$({1,3}, a) = {1, 2}, $\delta$({1,3}, b) = {} 3. 没有新的状态，结束，由于0和1是NFA的接受状态，Q里面有含有0和1的状态是DFA的接受状态，也就是F={ {0}, {1,2}, {1,3} } 至此，整个转换结束，对应的DFA： * 状态集合：Q = { {},{0},{1,2},{1,3} } * 转移函数：$\delta$({0}, a) = {1, 2}, $\delta$({0}, b) = {}， $\delta$({1,2}, a) = {1,2}, $\delta$({1,2}, b) = {1,3}, $\delta$({1,3}, a) = {1, 2}, $\delta$({1,3}, b) = {} * 输出状态集合：F={ {0}, {1,2}, {1,3} } 则转换后的DNA如图： https://www.cs.odu.edu/~toida/nerzic/390teched/regular/fa/figureshttps://img.qb5200.com/download-x/dfa1.jpg  有了这个手工操作的经验，上面这个例子里面，反复做一个动作： * 得到一个新的DFA元素，例如{1,2} * 考虑它接受一个输入，例如b，分别 * 考虑状态1接受b的转移状态集合，{} * 考虑状态2接受b的转移状态集合, {1,3} * 因此，{1,2}接受b后，转换到{1,3} 太啰嗦了，我们做一些简化： * 把转换后的DFA的元素标记为大写字母，例如T={1,2}, U={1,3}； * 把上面这个操作过程写成一个函数：move(T,b) * 那么上面这个过程就是：`move(T,b)=U` * 这个过程就是表示找到所有T里的元素在NFA里经过输入b后能**直接**到达的状态的集合U 进一步，如果在NFA里，某个s状态经过空转换$\epsilon$能到达的集合，我们标记为$\epsilon$-closure(s)。 例如： ``` -----> [1] / [0] \ ------> [2] ``` 那么，$\epsilon$-closure(0) = {1,2} 进一步 ``` ---->[3] / -----> [1]----->[4] / [0] \ ------> [2] ``` 那么，$\epsilon$-closure(0) = {1,2,3,4} 这么看来，$\epsilon$闭包是不是很形象。 有了$\epsilon$-closure(s)，我们当然可以对DFA里的T的每个元素做$\epsilon$-closure，于是就可以定义： * $\epsilon$-closure(T) = T里所有元素ti的$\epsilon$-closure(ti)的并集。 那么，我们上面的手工操作move(T,a)，之后，如果对应的NFA里也有$\epsilon，我们要达到最开始的转换NFA到DFA的两个目标之一： * 需要消灭所有的空输入 $\epsilon$ 我们就需要对上面讨论过的这个过程做升级： * 找到所有T里的元素在NFA里经过输入b后能**直接**到达的状态的集合U 也就是去掉**直接**两个字，升级成： * 找到所有T里的元素在NFA里经过输入b后能到达的状态的集合U 实际上，通过上面的讨论，经过烧脑，是可以理解到这个过程就是一个复合动作： * $\epsilon$-closure(move(T,b)) 于是，再经过烧脑，我们可以得到NFA转换成DFA的子集构造法(subset construction)算法： 1. T0=$\epsilon$-closure(q0); DFAState={}, DFAState[T0]=false; DFATransitioin={}; * 其中q0是NFA的初始状态 * 赋值为false，表示它还没有被标记 2. 开始循环 * 取出Q里的一个没有标记的元素，例如T。DFAState[T]=true立刻标记它，表示处理过了。 * 如果都标记了，退出循环 * 对输入的每个字符a * 计算U=$\epsilon$-closure(move(T,a)) * 如果U不在DFAState里面，就加入：DFAState[U]=false; * 加入转换函数：DFATransitioin[T,a]=U * 继续循环 从而，正则表达式可以转成NFA，再进一步转成DFA，实际上NFA转成NFA后，最糟的情况，原来需要n个状态，DFA需要2^n个状态（因为n个状态的幂子集的每个元素都可能是DFA的接受状态）。 为了加深印象，可以在这个在线工具里输入正则表达式直接看到对应的NFA和DFA的结果： [10] [Regex => NFA => DFA - CyberZHG](https://cyberzhg.github.io/toolbox/nfa2dfa) ## 0x04 Use State Machines 由于从Regex Expression到NFA到DFA，里面有一个地方是输入是用字符串的字符表示。会让人以为只有正则表达式需要DFA和NFA。 而实际上，我们可以在任何需要使用状态转换的地方用NFA和DFA。很自然的，需要考虑这些概念： * 有哪些状态？应该定义哪些状态？例如一个操作最简单的有Init/UnInit两种状态。 * 输入是什么？程序里的输入是「行为」，可能是用户点击，也可能是某个事件到达，在这些场景，你需要抽象这些输入，可以看成不同的「字符」，也可以根据它们需要转换的状态，看成是同一个「字符」。 * 输出是什么？当然是另外一个状态了。 * 跟正则表达式什么关系？ * 看法1: 没有关系，我们只关心状态转换是否是在允许的操作内，如果不是就是程序出现某种「未定义」行为，直接报错。这是消除Bugly的良方。 * 看法2: 一个由某些输入字符构成的字符串，表示了由UI操作、事件构成的操作序列，如果匹配，则表示这些操作集合是合法的，否则就是中间某个步骤是「未定义的」。 如何更好的写一个DFA构成的状态机代码？这里有一个Unity3D框架里的状态机的开发解释，很清晰的构架： [11] [Unity3D里的FSM(Finite State Machine)有限状态机](https://www.jianshu.com/p/7690b207ae92) 下面我们看一个例子，在实践上，如何设计状态机的转换。 首先，经过考虑，设计一组状态： * S={INIT,STARTING, PLAYING, STOP, ERROR} 其次，考虑每个状态可以到达哪些状态： * INIT -> [ STARTING ]， 初始状态可以到达开始中 * STARTING -> [PLAYING, ERROR]，开始中状态可以到达游玩中或者出错 * PLAYING -> [STOP, ERROR], 游玩中可以到达停止或出错 * ERROR -> [STOP]，出错状态，做好出错处理后停止 * STOP -> [INIT]，结束状态应该可以重置成初始化状态 因此，考虑初始和停止状态： * 初始状态：INIT * 停止状态集合：[STOP] 那么，可以逆向计算每个状态允许的前置状态集合(enableStates)： * INIT: [STOP] * STARTING: [INIT] * PLAYING: [STARTING] * STOP: [PLAYING, ERROR] * ERROR: [STARTING, PLAYING] **练习题1**：在这个状态转换中，Q、E、$\Sigma$，q_0, F 分别是什么？ **练习题2**：它是DFA，还是NFA？ **练习题3**：如果是NFA，它有空输入转换么？ **练习题4**：如果是NFA，试下转成DFA？ **练习题5**：画出NFA/DFA的转换图。 实践中，我们会按需写如下的状态转换函数，代码只是示例： ```JavaScript function EnterState(toState, onPreEnter, onAction, onPostEnter){ const fromState = this.state; if(enableStates[fromState].includes(toState)){ onPreEnter(fromState, toState); this.state = toState; onPreEnter(fromState, toState); return true; }else{ // log return false; } } ``` 实际上，如果考虑输入字符后，可以做一个更完备的版本： ```JavaScript function enableToState(fromState, context){ // 把context转换成愁绪的字符 const c = convertToAplha(fromState, context); // 根据fromState和c找到对应的可能输出集合 const toState = DFATransitioin(fromState, c); return toState; } function EnterState(toState, onPreEnter, onAction, onPostEnter){ const fromState = this.state; if(enableToState(fromState, context).includes(toState)){ onPreEnter(fromState, toState); this.state = toState; onPreEnter(fromState, toState); return true; }else{ // log return false; } } ``` 根据实际需要，可以做的简单，也可以做的细致，不同层度上保证程序的正确性。但是实际上，状态机在网络协议的开发中比较常见，例如经典的TCP状态转换图： [13] [rfc-793:TRANSMISSION CONTROL PROTOCOL](https://tools.ietf.org/html/rfc793)  有限状态机很有用，可是为什么大部分程序员平常写程序没用到它呢？ [12] [Why Developers Never Use State Machines]( https://skorks.com/2011/09/why-developers-never-use-state-machines/ ) >We seem to shy away from state machines due to misunderstanding of their complexity and/or an inability to quantify the benefits. But, there is less complexity than you would think and more benefits than you would expect as long you don’t try to retrofit a state machine after the fact. So next time you have an object that even hints at having a “status” field, just chuck a state machine in there, you’ll be glad you did. 这篇文章分析了可能的原因：「高估了它的复杂，以及低估了它的好处」，我觉的很有道理，特别是我发现在UI项目里使用严格的状态机管理状态后，程序的问题更容易被trace，也更能保证程序正确之后，我发现状态机确实好用。 ## 0x05 How using good theory leads to good programs? 而在这篇介绍Thompson NFA的文章里，作者的两段话很有意思： [6] [Regular Expression Matching Can Be Simple And Fast](https://swtch.com/~rsc/regexp/regexp1.html) >Historically, regular expressions are one of computer science's shining examples of **how using good theory leads to good programs**. They were originally developed by theorists as a simple computational model, but Ken Thompson introduced them to programmers in his implementation of the text editor QED for CTSS. Dennis Ritchie followed suit in his own implementation of QED, for GE-TSS. Thompson and Ritchie would go on to create Unix, and they brought regular expressions with them. By the late 1970s, regular expressions were a key feature of the Unix landscape, in tools such as ed, sed, grep, egrep, awk, and lex. >Today, regular expressions have also become a shining example of **how ignoring good theory leads to bad programs**. The regular expression implementations used by today's popular tools are significantly slower than the ones used in many of those thirty-year-old Unix tools. 这值得我们思考，程序是什么？ --end--