regex - NFA 到 RE Kleene 定理

Question

这是我的 NFA：

这是我的尝试。

• 创建新的开始和最终节点
• 接下来从左边消除第二个节点，这给了我 ab
• 接下来从右边消除第二个节点，它给了我 ab*a
• 接下来从左边消除第二个节点，它给了我 abb*b
• 接下来从右边消除第二个节点，它给了我 b+ab*a

这导致 abb b (b+ab a)*

这是正确的答案吗？

Answer 1

不，你不正确:(

_{你不需要创建开始状态。带-符号的第一个状态是开始状态。也a,b标签意味着a或b但不是ab}

_{有一个叫做Arden's theoram的定理，将有助于将 NFA 转换为 RE}

这个 NFA 的正则表达式是什么？

在您NFA中，DFA 的初始部分：

步骤1：

(-) --a,b-->(1)   

表示 (a+b)

step-2：接下来从 stat 1 到 2，注意state 2 正在接受 state final（有+符号）。

(1) --b--->(2+)

所以你需要 (a+b)b达到最终状态。

step-3：一个你处于最终状态2，任意数量的b被接受（任意数量表示一个或多个）。这是因为2带有标签的状态自循环b。

因此，b*在状态 2 上接受。

第4步：

实际上有两个循环state-2。

• b一个是我在step-3中描述的带有标签的自循环。它的表达式是b*

• 状态 2 上的第二个循环是通过状态 3。
  state-2 上第二个循环的表达式aa*b
  为什么是表达式aa*b？

  因为：

            a-  
            ||               ====>  aa*b
            ▼|   
  (2+)--a-->(3) --b-->(2+)   
  

因此，在第 3 步和第 4 步中，由于状态 2 运行的循环可以通过b标记或通过aa*b===> 循环返回(b + aa*b)*

所以你的 NFA 的正则表达式是：

(a+b) b (b + aa*b)*