显而易见的选择是耗尽所有可能的输入。我想我做到了。但我不太确定它是否有效,并且我没有违反任何非确定性有限自动机的规则。
我的 NFA 由以下给出:(ab u aab u aba)*
下面是我的图表。
我错过了什么吗?
显而易见的选择是耗尽所有可能的输入。我想我做到了。但我不太确定它是否有效,并且我没有违反任何非确定性有限自动机的规则。
我的 NFA 由以下给出:(ab u aab u aba)*
下面是我的图表。
我错过了什么吗?
你没有遗漏任何东西,但是 NFA 可以通过折叠路径和消除 λ 规则来大大简化。为了确定您的 NFA 是否决定了正则表达式表示的语言,您可以通过在转换图中追逐状态来非正式地争论。为了讨论 NFA,我将使用具有最终状态 {q 0 ,q 3 ,q 4 } 和初始状态 q 0的 δ 函数的以下定义
目标是表明 NFA 完全接受语言 (ab U aab U aba)*。为此,我们可以通过在 q 0处以 λ 开始并用尽图形中所有可能的转换来考虑接受的字符串,记录通过连接转换后的符号构建的字符串,并注意这样的字符串是否被接受。图中的路径表示连接;最终状态表明接受或分离;循环表示 Kleene 星。
从 q 0和 λ 我们可以在a上转换到 q 1或 q 2。在 q 1和a我们可以过渡到 q 2。因此,在 q 2上,我们要么有 a要么有aa,没有别的。从 q 2和a或aa我们可以过渡到b上的 q 3。因此,在 q 3处,我们要么有ab要么有aab,没有别的。从 q 3和ab或aab我们可以过渡到 qλ上的0或 a上的q 4。因此,在 q 3和ab或aab上,我们要么有ab要么aab或aba,没有别的。最后,在 q 4和aba上,我们可以在 λ 上转换到 q 0 。由于我们有ab或aab或aba并转换到起始状态,这意味着我们的推导可以重复零次或多次,并且我们已经用尽了可能的转换,我们得出结论 NFA 决定ab或aab或aba的 Kleene 闭包.
有更正式的方法表明给定的 NFA 决定了一种语言。但最简单的方法是用尽 NFA 的所有可能路径,在循环中引入 Kleene 闭包。形式化方法的一个示例是将 NFA 转换为正则表达式,然后公理化地推导获得的表达式和目标表达式的相等性。这在很大程度上是不必要的。
但是,您可能已经完全按照我刚刚写的内容完成了,这使得整个帖子变得不必要了。如果不是,我希望它展示了您可以用来说服自己 NFA 决定语言的那种非正式推理。