计算机基础之有限状态机
2022 os有限状态机（finite state machine），也叫有限自动机（finite automaton），是一台极简的计算机模型。
一个系统接受输入，改变自身状态，产生输出。在逐个接受输入的字符的过程中，机器状态会发生多次改变，最终会停止在某个状态，并有输出产生。如果对于所有的输入，机器状态的数目有限，称为有限状态机。
有限状态机可以分为两类：确定有限状态机（DFA）和非确定有限状态机（NFA）。
DFA
确定有限状态机（DFA，Deterministic finite automaton），一个状态的一个输入只有一个转换规则；每个状态都包含了所有的输入的规则转换。
上图的 S1 是开始状态，也是接受状态。该图可以接受的字符串有1, 11, 11…, 00, 010, 1010等等。
NFA
非确定有限状态机（NFA，Non-deterministic finite automaton），对一个输入可能有不同的转换规则；状态可能会缺少某种输入的转换规则。
