- 你如何找到最小的确定性 FSM?
- 有没有办法标准化非确定性 FSM?
- 是否有线性时间限制算法来找到给定机器的最小 FSM?
- 有没有办法查看两个 FSM 是否等效?
这不是一个家庭作业问题。我正在看这个系列讲座,只是很好奇。
这不是一个家庭作业问题。我正在看这个系列讲座,只是很好奇。
由于所有非确定性 FSM 都有一个对应的确定性 FSM,因此对 1 和 2 的答案应该是相同的。
如果您想了解更多信息,请获取 Michael Sipser 的《计算理论导论》,这是一本学习这些知识的非常棒的书。Sipser 知道他在谈论什么以及如何很好地沟通。
一些非正式的答案可以为您提供想法,详细的证明请阅读一本关于自动机的好书,例如这本或其他答案中提到的那些。而且我很确定您可以找到在线材料来回答您的所有问题。
该过程是消除重复状态(或合并等效状态)。你知道状态和转换是生成字符串的关键。基本上,重复的状态不会使生成的语言更大或更小。该算法从始终具有生成lamda(空字符串)能力的最终状态开始,递归地更新表示状态生成能力的表,最后合并那些没有区别的状态。
NFA 的归一化 DFA 是使用 NFA 的不同状态集合作为 DFA 的状态,例如 {state0} -(1)-> {state1, state2} 去除非确定性部分,没有办法避免作为 DFA 的状态爆炸必须这样做来表示语言。
我记得最好的一个是 O(NLogN) 通过在西安大略大学教授的一些论文中重复使用信息的一些技巧,并且怀疑是否存在更好的。我相信经典的是 O(N^2)。
是的。获取最小的,通过访问字符串(可以从开始状态到达状态的字符串,这几乎是那里的状态的真实“名称”)对状态进行编码,并验证转换图。虽然可能有更好的方法,但在 bigO 上不会有太大的不同。
从第 2.5 节开始检查“编译器设计基础”。可在线免费使用。http://www.diku.dk/hjemmesider/ansatte/torbenm/Basics/basics_lulu.pdf
它包括将 NFA 转换为 DFA 并最小化 DFA。NFA 可以在转换为 DFA 时呈指数增长。
“...任何正则语言(可以用正则表达式、NFA 或 DFA 表示的语言)都具有唯一的最小 DFA。因此,我们可以通过将正则表达式(或 NFA 或 DFA)都转换为最小 DFA 来确定等价性并比较结果。”