带输出的有限自动机

Moore型有限自动机

  一个Moore型有限自动机是一个五元组(Q,q_0,\Sigma,\Gamma,\delta,G)，其中：

1. 所有状态的集合Q
2. 起始状态q_0\in Q
3. 输入字母表\Sigma
4. 输出的字符表\Gamma
5. 状态转移函数\delta:Q\times\Sigma\rightarrow Q，指示如何从一个状态和当前输入字符转移到下一个
6. 输出函数G:Q\rightarrow \Gamma，指示一个状态对应输出字符表中的哪个字符输出

注意这里把输入符号表叫做字母表(alphabet)，而输出符号表叫做字符表(character)
  Moore型有限自动机是一种特殊的有限自动机，和普通的DFA不同，Moore机允许输出，这里并不确切考虑输出的方式，比如是打印在纸上还是显示在屏幕上。在Moore机中，每个状态会映射到输出字符表中的一个字符，当执行到该状态时就会输出该状态对应的字符，由于这一点，因此Moore机没有停机状态，当输入字符串的最后一个字符并且输出字符串被输出完毕时，Moore机才会终止运行。注意到Moore机的输出应当比输入字符串的长度多1，因为对于有n个字符的可以被接受的字符串，带上起始状态后接受路径总有n+1个状态，用类似如下的图示描述Moore机：

其中每个状态由q_{no}/output构成，no代表当前状态序号，而output代表进入该状态会产生什么输出，比如，字符串aabbaba在上面的Moore机中就会输出10100101，注意第一个1是由于起始状态是1，而自动机不需要读入任何字母就会进入起始状态，也就是说Moore机的第一个输出字符总是起始状态代表的字符

Moore机的应用

语言识别

  Moore机不能像DFA那样识别语言，但是可以通过其他的方式来识别字符串，比如对于

这个机器可以帮助我们发现一个字符串中aab出现的次数，注意只有到q_3，也就是字符串读取了两个a和一个b后才会输出1，因此只需要计算输出字符串中1的个数，就知道aab出现的次数了

Mealy型有限自动机

  Mealy机的定义和Moore机几乎一样，惟一的区别是，Moore机在抵达一个状态的时候才会输出，而Mealy机在前往一个状态的过程中，也就是在途径一个边的时候输出，正因为这一点，所以Mealy机的输出和输入字符数相同，因为经历的边的数量就是字符串的长度，我们用类似如下的图示来表示Mealy机

每条边被i/o标记，其中i代表这条边对应的输入字母，o代表经过这条边时要输出的字符，aaabb在上面机器中的输出就是01110

Mealy机的应用

按位取反

  假设输入字母表是\Sigma=\lbrace 1,0 \rbrace，那么很容易构造出一个输出是输入按位取反的Mealy机：

递增

  假设输入字母表是\Sigma=\lbrace 1,0 \rbrace，可以构造出一个Mealy机，让他的输出是原输入大小+1。注意，输入和输出都是和真实数字相反，比如想要输入2对应的二进制10，实际应该输入的是01，输出也是这样。

对于11的二进制1011，反过来也就是1101，输入机器得到输出0011，反过来就是1100，也就是12的二进制形式。

加减法器

  鉴于Mealy机具有取反和递增的能力，这让他具备了基础算术运算的能力，结合上面两点，可以构造出加法器和减法器的数学模型，比如，对于两个二进制字符串的减法运算遵循以下规则

如果a和b是二进制字符串，那么可以通过以下两个步骤得到a-b

1. 让a加上b按位取反的值，忽略任何溢出的进位
2. 让结果递增1

EXAMPLE

\begin{aligned}
14-5&=1110-0101 \\
&=1110+1010+1\\
&=[1]1001\\
&=9(去掉进位溢出的1)
\end{aligned}

语言识别

  和Moore机一样，Mealy机不能直接识别某个语言，但是通过某种办法，可以让Mealy机去根据输入字符串来"回答一些问题"，比如对于

这个机器每读到两个或两个以上的b或者a就会输出1，比如ababbaab会输出00001010，而aaa或者bbb都会输出011，因为连续三个a或b中包含两个连续的a或b，因此，数一下最终输出中1的个数，就能知道字符串中出现了多少次aa或bb

Moore=Mealy

  鉴于这两者都不能在传统意义上识别语言，定义它们的等价用一种别的方法，也就是如果对同一个输入字符串两者产生相同的输出，则两机器等价，问题是这似乎不可能，因为Moore机的输出总要比Mealy机多一个，解决这个问题的方法简单粗暴——直接忽视Moore机的第一个输出字符

DEFINITION
令M_e是一个Mealy机，M_o是一个Moore机，令x是M_o起始状态的输出字符，如果M_o的输出恰巧等于x和M_e输出的拼接，则说M_e和M_o等价

定理1：如果M_o是一个Moore机，则存在一个Mealy机M_e与其等价
证明：对于M_o的每个状态q，获取这个状态的所有输入边的集合E，并且把q上所标记的输入字符转移到E的每个元素上，之后去掉q上标记的输出字符

例如：

转换为

对每个状态都执行该操作，就可以得到对应的Mealy机

定理2：如果M_e是一个Mealy机，则存在一个Moore机M_o与其等价
证明：不能简单地执行定理1证明中的反向操作来得到定理2的算法，因为在定理2中(假设\Sigma=\lbrace a,b\rbrace)，M_e的每个状态q_n可能存在两个标记了不同输出字符的输入边，对于这种，我们需要把状态q分成两部分q_n^1和q_n^2，其中标记了a的输入边重新导向q_n^1，标记了b的输入边重新导向q_n^2，之后在把原先q_n上的所有输出边原封不同的搬到q_n^1和q_n^2上，比如对于

变成(注意这两张图都只表示了一小部分)

有一种情况比较特殊，也就是当这些有两个不同输出字符标记的输入边的其中一个是循环的时候：

这时候如果要进行转换，需要转换成这样

因为原先的b^\ast有完全不读入任何字符和读入任意大于等一一个b两种可能性，因此我们必须全都考虑到，q^1/0到q_1的边应对的是不读入任何字符的情况，而下面连接到q^2的b边和q^2上面的b循环处理的是读入任意大于等一一个b的情况。

定理2与定理1一起，可以证明

注意从M_e到M_o，可能会多出别的的状态和边，而反过来则不会

不同自动机的区别一览