state-machine - 在有限状态机中，状态可以生成事件吗？

Question

在有限状态机中，一个状态S1是否可以产生一个事件，那么这个事件会触发从这个状态S1到另一个状态S2的转换？

Answer 1

从计算理论的角度来看，“纯”有限状态机的唯一功能是将输入字符串转换为 N 选之一(在大多数插图中，它是二选一(接受与拒绝)选择，但 N 工作的较大有限值在概念上是相同的)。如果两个纯有限状态机对于任何输入字符序列都将返回相同的 one-of-N 结果，则它们是等价的。纯有限状态机的升级是有限状态转换器，其中每个边缘都可以将任意数量的字符发送到输出流，这对任何 future 的状态转换都没有影响。如果对于任何输入字符序列它们将生成相同的输出字符序列并返回相同的 N 中的一个结果，则两台这样的机器是等价的。

给定两个纯有限状态机或两个纯有限状态转换器，可以在合理的限定时间内确定它们是否等效(如果两个转换器，其中较小的一个有 N 个状态，将产生相同的输出序列对于最多 2N 个字符的任何输入序列，对于任何长度的任何输入序列，它们都会为任何输入序列产生相同的输出序列)。如果允许状态机生成可以反过来影响其输入的“事件”，则可以使用相同的方法，但是只有当两台机器生成完全相同的事件序列并且假设所有输入组合都无论生成的事件如何，都是可能的。另一方面，如果存在某种类型的事件可以以某种方式影响状态机的输入但机器的用户不感兴趣，或者如果某些事件序列意味着某些输入序列不会发生，可能很难(甚至根本不可能)确定两台机器在用户不关心的方式上可能有所不同，但在用户关心的方式上是否相同。

触发影响其输入的事件的状态机在现实世界中通常很有用，但无法使用适用于更简单机器的方法来分析此类机器。实际上，输出和输入之间的联系需要被视为状态机的一部分；许多这样的链接机制都有许多状态，这完全使它们所附加的 DFA 中的潜在状​​态数量相形见绌(如果它有界的话)。