0

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

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

在此处输入图像描述

我错过了什么吗?

4

1 回答 1

1

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

  • δ(q 0 ,a) = {q 1 ,q 2 }
  • δ(q 1 ,a) = {q 2 }
  • δ(q 2 ,b) = {q 3 }
  • δ(q 3 ,a) = {q 4 }
  • δ(q 3 ,λ) = {q 0 }
  • δ(q 4 ,λ) = {q - }

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

从 q 0和 λ 我们可以在a上转换到 q 1或 q 2。在 q 1a我们可以过渡到 q 2。因此,在 q 2上,我们要么有 a要么有aa,没有别的。从 q 2aaa我们可以过渡到b上的 q 3。因此,在 q 3处,我们要么有ab要么有aab,没有别的。从 q 3abaab我们可以过渡到 qλ上的0或 a上的q 4。因此,在 q 3abaab上,我们要么有ab要么aababa,没有别的。最后,在 q 4aba上,我们可以在 λ 上转换到 q 0 。由于我们有abaababa并转换到起始状态,这意味着我们的推导可以重复零次或多次,并且我们已经用尽了可能的转换,我们得出结论 NFA 决定abaababa的 Kleene 闭包.

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

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

于 2011-10-21T05:16:39.620 回答