finite-automata - 如何确定我的 NFA 是否正确？

Question

显而易见的选择是耗尽所有可能的输入。我想我做到了。但我不太确定它是否有效，并且我没有违反任何非确定性有限自动机的规则。

我的 NFA 由以下给出：(ab u aab u aba)*下面是我的图表。

我错过了什么吗？

Answer 1

你没有遗漏任何东西，但是 NFA 可以通过折叠路径和消除 λ 规则来大大简化。为了确定您的 NFA 是否决定了正则表达式表示的语言，您可以通过在转换图中追逐状态来非正式地争论。为了讨论 NFA，我将使用具有最终状态 {q ₀ ,q ₃ ,q ₄ } 和初始状态 q _{0的 δ 函数的以下定义}

• δ(q ₀ ,a) = {q ₁ ,q ₂ }
• δ(q ₁ ,a) = {q ₂ }
• δ(q ₂ ,b) = {q ₃ }
• δ(q ₃ ,a) = {q ₄ }
• δ(q ₃ ,λ) = {q ₀ }
• δ(q ₄ ,λ) = {q _- }

目标是表明 NFA 完全接受语言 (ab U aab U aba)*。为此，我们可以通过在 q ₀处以 λ 开始并用尽图形中所有可能的转换来考虑接受的字符串，记录通过连接转换后的符号构建的字符串，并注意这样的字符串是否被接受。图中的路径表示连接；最终状态表明接受或分离；循环表示 Kleene 星。

从 q ₀和 λ 我们可以在a上转换到 q ₁或 q ₂。在 q ₁和a我们可以过渡到 q ₂。因此，在 q ₂上，我们要么有 a要么有aa，没有别的。从 q ₂和a或aa我们可以过渡到b上的 q ₃。因此，在 q ₃处，我们要么有ab要么有aab，没有别的。从 q ₃和ab或aab我们可以过渡到 qλ上的₀或 a上的q ₄。因此，在 q ₃和ab或aab上，我们要么有ab要么aab或aba，没有别的。最后，在 q ₄和aba上，我们可以在 λ 上转换到 q _{0 。}由于我们有ab或aab或aba并转换到起始状态，这意味着我们的推导可以重复零次或多次，并且我们已经用尽了可能的转换，我们得出结论 NFA 决定ab或aab或aba的 Kleene 闭包.

有更正式的方法表明给定的 NFA 决定了一种语言。但最简单的方法是用尽 NFA 的所有可能路径，在循环中引入 Kleene 闭包。形式化方法的一个示例是将 NFA 转换为正则表达式，然后公理化地推导获得的表达式和目标表达式的相等性。这在很大程度上是不必要的。

但是，您可能已经完全按照我刚刚写的内容完成了，这使得整个帖子变得不必要了。如果不是，我希望它展示了您可以用来说服自己 NFA 决定语言的那种非正式推理。