# 词法分析 ## 有限状态机（FA） 就是我们一般说的状态机，也叫FSM或者FSA ## 非确定性有限状态机（NFA） - 一个节点的多个出弧可以接收同一个输入，即**单输入导出多个可能状态** - 弧可以接收空输入，即**空输入导出多个可能状态** - 上述两条造成了NFA瞬时状态的不确定性（接收同一输入后，可能处在不同状态）   ## 确定性有限状态机（DFA） - 一个节点的每个出弧接收的输入都不同，即**单输入导出确定状态** - 不允许出现接收空输入的弧 - 上述两条保证了DFA瞬时状态是确定的 **一定存在等价的一组DFA和NFA**。使用枚举所有情况的算法可将NFA转为DFA，如：  （其中d指digits即数字，E指字母E即科学计数法的前导标志）