《编程珠玑（续）（修订版）》—第2章2.2节有穷状态机模拟器

本节书摘来自异步社区《编程珠玑（续）（修订版）》一书中的第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”。

执行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。