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

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

4

4 回答 4

8

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

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

于 2009-07-09T18:51:38.613 回答
6

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

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

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

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

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

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

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

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

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

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

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

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

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

于 2009-12-02T03:36:48.977 回答