本节书摘来自异步社区《编程珠玑（续）（修订版）》一书中的第2章，第2.2节有穷状态机模拟器，作者【美】Jon Bentley，更多章节内容可以访问云栖社区“异步社区”公众号查看。
2.2 有穷状态机模拟器有穷状态机（FSM）是计算的一种优雅的数学模型和有用的实践工具，它在程序设计语言的词法分析、通信协议以及简单硬件设备等许多应用领域都有广泛的用途。Wulf、Shaw、Hilfinger和Flon在他们合著的Fundamental Structures of Computer Science③一书（Addison-Wesley出版社1981年出版）的1.1节讨论了这一主题。
作为例子，他们考虑这样一个简单的任务——“抑制”比特流中所有新出现的1：
Input: 011010111 Output: 001000011紧跟在0后面的1被改成0，输入流中的所有其他比特位不变。
下面的两状态自动机在其状态中对最后一个输入比特进行编码：“LIZ”表示“Last Input Zero”，而“LIO”表示“Last Input One”。
指向LIZ的横向箭头表明这是初始状态。从LIZ到LIO的弧线的意思是，如果自动机当前处于状态LIZ且输入是一个1，则输出一个0并进入状态LIO。执行FSM的程序使用两个主要数据结构。如果FSM包含弧线
那么下面的等式成立： trans[State1, InSym] == State2 out[State1, InSym] == OutSym名字trans表示状态转换，out表示输出符号。
上面描述的自动机和输入编码如下：
LIZ 0 LIZ 0 LIZ 1 LIO 0 LIO 0 LIZ 0 LIO 1 LIO 1 start LIZ 0 1 1 0 ...前4行表示FSM中的4条边。第一行说，如果自动机当前状态为LIZ且输入为0，那么下一个状态是LIZ并输出0。第五行确定初始状态，之后的行是输入数据。
下面的程序按上面描述的形式执行FSM。
run == 1 { print out[s, $1]; s = trans[s, $1] } run == 0 { if ($1 == "start") { run = 1; s = $2 } else { trans[$1, $2] = $3; out[$1, $2] = $4 } }该程序有两个主要的模式。起初，变量run值为零。在这个模式下，将自动机的转换添加到数组trans和out中。当输入的某一行的第一个字段是字符串"start"时，程序将相应的初始状态存放到s中，然后切换到运行模式。然后每步的执行都将产生输出并改变状态，每步转换后的状态可以看成是当前输入（$1）和当前状态（s）的函数。
这个微型的程序有很多缺点。例如，对于未定义的转换，它做出的反应将是灾难性的。事实上，这个程序顶多适合个人使用。另一方面，它为创建更健壮的程序提供了便利的基础，见习题2。
相关资源：编程珠玑（第2版•修订版）2015最新 完整扫描.pdf版