当我们从 nfa 转换为 dfa 时，可能会出现如下图所示的结果......我的问题是，是否有必要从状态 {4} 写入它会变为零状态？我的意思是不显示 {4} 的输入符号 1 与右下图相同？或没有？
问问题
1515 次
3 回答
2
这是一个约定俗成的问题。就我个人而言，我不希望用不必要的状态将我的 DFA 弄乱，特别是因为通过 NFA 转换获得的 DFA 无论如何都会变得相当复杂，而且由于它是确定性的，我们知道任何未显示的转换都必须是无效的。
但是，我经历过学术界的许多人教授/使用其他约定，并要求明确显示所有转换。在担任 TA（导师）时，我实际上与一位教授讨论过这个问题——他希望我们的导师在 DFA 中缺少转换的最终测试中扣分，但我说服他为此扣分是不公平的。
于 2012-06-04T21:19:42.953 回答
1
没有必要写 {4}-> 0 转换，因为自动机已经接受了这个词。这种转变仅意味着这对我们的解决方案“没有意义”。但是对于细节，给出它是有用的，以展示整个自动机。
于 2012-06-04T21:11:30.813 回答
0
仅当您尝试绘制 MinimalFA (MFA) 时才重要。
实际上，您可以从单个 NFA 生成无限数量的 DFA，每个 NFA 的状态数不同。
如果你去掉图中的“Dead States”，你就会得到 MFA。如果你只想要一个 DFA，这个数字就可以了
于 2013-07-18T15:48:05.123 回答