自动售货机模型

以自动售货机为例。机器接受 5 分、10 分和 25 分硬币；若总额达到 30 分或超过 30 分，就退还超过的部分。收够 30 分之后，按橙色按钮给橘子汁，按红色按钮给苹果汁。

状态 $s_i$ 表示机器已经收集了 $5i$ 分钱。这样金额变化可以转化为状态变化，而“退钱”和“出饮料”就作为输出。

同一个状态机既可以用状态表表示，也可以用状态图表示。状态图中的边一般标成“输入，输出”的形式。

带输出的有限状态机

带输出的有限状态机记作 $M=(S,I,O,f,g,s_0)$ ，其中：

• $S$ 是有限状态集。
• $I$ 是有限输入字母表。
• $O$ 是有限输出字母表。
• $f:S\times I\rightarrow S$ 是转移函数。
• $g:S\times I\rightarrow O$ 是输出函数。
• $s_0\in S$ 是初始状态。

如果输入串为 $x_1x_2\cdots x_n$ ，那么状态序列和输出序列都可以递归得到。设初始状态为 $s_0$ ，读入第 $k$ 个输入后有

同时输出为

所以这个模型关注的是整段输入对应的整段输出，而不只是最终停在哪个状态。

状态表与状态图

状态表把转移函数 $f$ 和输出函数 $g$ 分开列出，状态图则把两者合并到边上。

在状态图里，边上的 $1,0$ 可以理解为读入 $1$ 时输出 $0$ ，并沿这条边转移。读图时要注意：输出发生在转移边上，而不是发生在目标状态上。

输出函数也可以扩展到字符串。直观地说，就是把 $f$ 和 $g$ 反复复合，读入一整个输入串后得到一整个输出串。

应用和语言接受

系统的“记忆”可以压缩成有限个状态时，就可以用状态机描述。

带输出的状态机也称 transducer，它把输入串变换成输出串。只关心输入是否被接受时，可以省去输出，用终结状态区分接受与拒绝。