在计算理论中，什么是米利机？

在米利机中，输出符号取决于当前输入符号和机器的当前状态。

输出用每个输入符号表示，每个状态用“/”分隔。

米利机可以用6元组来描述

(Q, q0, Σ, O, δ, λ')

其中：

• Q：有限状态集
• q0：机器的初始状态
• Σ：有限输入字母表
• O：输出字母表
• δ：转移函数，其中 Q × Σ → Q
• λ'：输出函数，其中 Q × Σ → O

米利机的输出长度等于输入长度。

示例1

输入 - 11

转移 - δ (q0,11) => δ(q2,1) => q2

输出 - 00（q0到q2的转移输出为0，q2到q2的转移输出也为0）

状态转换图如下：

解释

• **步骤1** - q0是起始状态，输入‘0’，它进入状态q1并产生输出‘0’；输入‘1’，它进入状态q2并产生输出‘0’。
• **步骤2** - q1输入‘0’保持在q1状态并产生输出‘0’；输入‘1’进入q2状态并产生输出‘1’。
• **步骤3** - q2输入‘1’保持在q2状态并产生输出‘0’；输入‘0’进入状态q1并产生输出‘1’。

米利机的状态表如下：

示例2

设计一个用于二进制输入序列{0,1}的米利机。

如果输入具有子串101，则输出为A。

如果输入具有子串110，则输出为B；否则，输出为C。

状态转换图如下：

状态转移表如下：

Bhanu Priya

更新于：2021年6月11日

3K+ 次浏览

启动你的职业生涯

通过完成课程获得认证

开始学习