自动机之Moore机自动机之Moore机|自动机教程

【自动机之Moore机】摩尔机是一种有限状态机，其中下一个状态由当前状态和当前输入符号决定。给定时间的输出符号仅取决于机器的当前状态。摩尔机器可以由6个元组（Q，q0，∑，O，δ，λ）描述，其中，

Q: finite set of states q0: initial state of machine ∑: finite set of input symbols O: output alphabet δ: transition function where Q × ∑ → Q λ: output function where Q → O

范例1：
摩尔机的状态图是

文章图片
摩尔机的转换表是：

文章图片
在上述摩尔机器中，输出用/分隔每个输入状态。 Moore机器的输出长度大于输入长度1。
输入：010
过渡：δ（q0.0）=> δ（q1.1）=> δ（q1.0）=> q2
输出：1110（1代表q0, 1代表q1，再次1代表q1, 0代表q2）
范例2：
设计摩尔机，以生成给定二进制数的1的补码。
解决方案：要生成给定二进制数的1的补码，简单的逻辑是，如果输入为0，则输出为1，如果输入为1，则输出为0。这意味着存在三种状态。一种状态是开始状态。第二种状态用于将0用作输入并产生输出1。第三种状态用于将1用作输入并产生输出0。
因此，摩尔机器将是

文章图片
例如，取一个二进制数1011然后

输入值		1	0	1	1
州	00	22	11	22	22
输出量	0	0	1	0	0

因此，我们得到00100作为1011的1的补码，我们可以忽略初始0，而得到的输出是0100，它是1011的1的补码。事务表如下：

文章图片
因此摩尔机器M =（Q，q0，∑，O，δ，λ）; 其中Q = {q0，q1，q2}，∑ = {0，1}，O = {0，1}。过渡表显示了δ和λ函数。
范例3：
针对二进制输入序列设计摩尔机器，以便如果它具有子字符串101，则机器输出A；如果输入具有子字符串110，则输出B，否则输出C。
解决方案：对于设计这样的机器，我们将检查两个条件，分别是101和110。如果得到101，则输出将为A，如果我们识别为110，则输出将为B。对于其他字符串，输出将是C。
部分图将是：

文章图片
现在，我们将为每个状态插入0和1的可能性。因此，摩尔机变成：

文章图片
范例4：
构造一个Moore机器，该机器确定输入字符串是否包含1的偶数或奇数。如果字符串中的偶数个数为1，则机器应给出1作为输出，否则为0。
解：
摩尔机将是：

文章图片
这是必需的摩尔机。在此机器中，状态q1接受1的奇数，状态q0接受1的偶数。对零的数量没有限制。因此，对于0输入，自环可应用于两种状态。
范例5：
设计一个具有输入字母{0，1}和输出字母{Y，N}的Moore机器，如果输入序列包含1010作为子字符串，则输出Y，否则输出N。
解：
摩尔机将是：