computer-science - 如何规范化有限状态机？

Question

1. 你如何找到最小的确定性 FSM？
2. 有没有办法标准化非确定性 FSM？
3. 是否有线性时间限制算法来找到给定机器的最小 FSM？
4. 有没有办法查看两个 FSM 是否等效？

这不是一个家庭作业问题。我正在看这个系列讲座，只是很好奇。

Answer 1

由于所有非确定性 FSM 都有一个对应的确定性 FSM，因此对 1 和 2 的答案应该是相同的。

如果您想了解更多信息，请获取 Michael Sipser 的《计算理论导论》，这是一本学习这些知识的非常棒的书。Sipser 知道他在谈论什么以及如何很好地沟通。

Answer 2

一些非正式的答案可以为您提供想法，详细的证明请阅读一本关于自动机的好书，例如这本或其他答案中提到的那些。而且我很确定您可以找到在线材料来回答您的所有问题。

• 你如何找到最小的确定性 FSM？

该过程是消除重复状态（或合并等效状态）。你知道状态和转换是生成字符串的关键。基本上，重复的状态不会使生成的语言更大或更小。该算法从始终具有生成lamda（空字符串）能力的最终状态开始，递归地更新表示状态生成能力的表，最后合并那些没有区别的状态。

• 有没有办法标准化非确定性 FSM？

NFA 的归一化 DFA 是使用 NFA 的不同状态集合作为 DFA 的状态，例如 {state0} -(1)-> {state1, state2} 去除非确定性部分，没有办法避免作为 DFA 的状态爆炸必须这样做来表示语言。

• 是否有线性时间限制算法来找到给定机器的最小 FSM？

我记得最好的一个是 O(NLogN) 通过在西安大略大学教授的一些论文中重复使用信息的一些技巧，并且怀疑是否存在更好的。我相信经典的是 O(N^2)。

• 有没有办法查看两个 FSM 是否等效？

是的。获取最小的，通过访问字符串（可以从开始状态到达状态的字符串，这几乎是那里的状态的真实“名称”）对状态进行编码，并验证转换图。虽然可能有更好的方法，但在 bigO 上不会有太大的不同。

Answer 3

• 如果给定一些确定性 FSM，那么您可以使用 O(n ² ) 中的一个非常简单的算法找到一个等价的、最小的 FSM；Hopcroft 的算法在 O(n log n) 中完成。在这里你会找到两者的描述。您可以通过最小化它们并检查它们是否相同来检查 A 和 B 是否相等。
• 如果给你一些不确定的 FSM，那么找到一个等价的、最小的就是PSPACE-complete。换句话说，没有好的算法是已知的，并且推测它不存在。检查两个非确定性自动机的等价性也是 PSPACE 完备的。因此，除非出现非常不可能的突破，否则您应该将自动机转换为确定性自动机（这需要很多时间），然后执行检查。
• 您可以将非确定性 FSM 转换为具有指数数量状态的确定性 FSM。这是不可避免的。练习（不难！）：由末尾第 n 个字母为“a”的单词组成的语言可以使用具有 n 个状态的非确定性 FSM 来识别，而使用小于 2的确定性 FSM则无法识别ⁿ个状态。在一般情况下不能打破指数界限。

Answer 4

从第 2.5 节开始检查“编译器设计基础”。可在线免费使用。http://www.diku.dk/hjemmesider/ansatte/torbenm/Basics/basics_lulu.pdf

它包括将 NFA 转换为 DFA 并最小化 DFA。NFA 可以在转换为 DFA 时呈指数增长。

“...任何正则语言（可以用正则表达式、NFA 或 DFA 表示的语言）都具有唯一的最小 DFA。因此，我们可以通过将正则表达式（或 NFA 或 DFA）都转换为最小 DFA 来确定等价性并比较结果。”