有限状态机在本科数电实验接触过, 但是最近在做LeetCode第8题时才发现其妙用. FSM通常可以用5元组\((Q, \Sigma, T, q_0, F)\)表示: Q表示有限的状态集合, \(\Sigma\)表示有限的输入集合, T表示状态转移函数, \(q_0\)表示初始状态, F表示结束状态.
Deterministic Finite Automaton
如果不知道DFA, 那么在做诸如LC 8/65等题时, 面对浩如烟海的corner case, 即使写出了代码, 想必也是一团乱麻.
以LC 65题为例, 给一个包含大小写英文字母/数字/+/-/.的字符串, 判断其是否是一个有效的数字.
DFA的思路是: 开始是自动机处于初始状态, 之后顺序读取每个字符, 根据当前状态和该字符的转移规则转移到下一个状态, 读完整个字符串后如果自动机处于某个可接受状态, 则合法. 如果读取过程中转移失败或者最终自动机处于非接受状态, 则非法.
第一步就是要枚举所有的可能状态, 通常对于字符串匹配问题可以考虑用字符串的不同部分作为状态集合. 例如本题中一个合法的字符串应当包含以下部分:
- 符号位+/-: 如果存在, 其后必须跟着数字或小数点
- 整数部分: 若干0-9组成的串
- 小数点: 两侧至少有一侧是数字
- 小数部分: 与整数部分相同
- 指数部分: e/E, 符号位, 整数部分
所以状态集合包括:
- 初始状态
- 符号位
- 整数部分
- 左侧有整数的小数点
- 左侧无整数的小数点
- 小数部分
- 字符e/E
- 指数部分符号位
- 指数部分的整数部分
小数点有些特殊, 其两侧至少一侧有数字才合法.
通常来讲小数点可以转移到e或小数部分, 但是对于左侧没有整数的小数点,
其右侧必须有数字, 不能转移到e, 只能转移到小数部分,
否则违背了小数点的规则. 例如.e1就是非法的,
3.e1就是合法的. 因此小数点的状态需要分为2类:
左侧有整数以及左侧无整数. 那么为什么不按照小数点右侧有无数字来分类呢?
我认为最大原因在于状态机是不能回退的, 即如果已经访问到了小数点右侧,
那么无法结合其左侧状态进行下一步的转移.
假设右侧有数字的小数点为a, 右侧没有数字的小数点为b.
例如对于初始状态的输入.,
能否转移到a或b都是不确定的,
因为此时无法判断小数点右侧是否有数字. 如果采用左侧的划分方式,
转移则是确定的.
第二步需要找到初始状态0和可接受状态2/3/5/8.
最后需要根据合法字符串的格式定义转移规则, 并画出转移图: 
为了写代码方便,
通常用unordered_map<state, unordered_map<cur, state>>来表示状态转移表,
只要将上述转移图翻译成代码即可.
除了算法题的应用, FSM与KMP算法和正则表达式都有着密切关联.
