5

我在这个网站上发现了同样的问题,答案是描述如何将 NFA 转换为 regex 的 PDF。但这不起作用,因为这种方法有一些条件:

  1. 有从初始状态到所有其他状态的转换,并且没有到初始状态的转换。
  2. 有一个接受状态,只有转换进入它(并且没有传出转换)。
  3. 接受状态不同于初始状态。
  4. 除了初始状态和接受状态外,所有其他状态都通过转换连接到所有其他状态。特别是,每个状态都有到自身的转换。

在我的示例中,开始状态只是进入下一个状态,而不是所有状态(例如,q0 进入 q1 但没有进入 q2、q3),并且有到开始状态的转换。

那么将 NFA 转换为正则表达式的最简单方法是什么?我没有给出 NFA 示例,因为我没有一个特定的示例,这只是一个一般性问题,因为我遇到了这种 DFA,其中开始状态与所有状态不相关,并且是过渡到开始状态。

我想要一个通用算法来转换这种 NFA。

4

1 回答 1

4

答案是假设这些条件,因为可以修改任何 NFA 以适应这些要求。

对于任何类型的 NFA,您都可以添加一个新的初始状态 q 0,它具有到原始初始状态的 epsilon-transition,并且还使用一个称为 ∅ 的附加转换符号(他们称之为空集符号,假设是一个符号不匹配来自原始 NFA 的任何符号)从它到任何其他状态,然后使用这个新状态作为新的初始状态。请注意,这不会更改原始 NFA 接受的语言。这将使您的 NFA 满足第一个条件。

对于任何类型的 NFA,您都可以添加一个新的接受状态 q a,它具有来自原始 NFA 中所有接受状态的 epsilon-transition。然后将此标记为唯一的接受状态。请注意,这不会更改原始 NFA 接受的语言。这将使您的 NFA 满足第二个条件。

通过上述构造,通过设置 q 0 != q a,它满足第三个条件。

在您提供的链接中,第四个条件通过一个名为∅(空集符号)的特殊转换符号来解释,原始 NFA 中的任何实际字母都无法匹配。因此,您可以使用这个新符号添加从每个状态到任何其他状态的转换。请注意,这不会更改原始 NFA 接受的语言。

所以现在 NFA 已经被修改为满足这四个要求,你可以应用那里的算法将 NFA 转换为正则表达式,它将接受与原始 NFA 相同的语言。

编辑以回答进一步的问题

要在评论中回答您的问题,请考虑具有两个状态 q A和 q B的 NFA 。q A是初始状态,也是唯一的接受状态。我们有一个从 q A到其自身的转换,符号为 0,1。我们也有从 q A到 q B的转换,符号为 1。最后,我们有从 q B到 q A 的转换,符号为 0。

可视化:

0,1    
  | 1
->q A ----->q B
  ^ |
  |-------|
     0

步骤 2. 当我们对 NFA 进行归一化时,只需放入指向 q A的新初始状态 (q init ),并从 q A放入新的接受状态 (q acc ) 。

步骤 3. 我们要删除 q A。所以 q A是算法中的 q rip(在第 3 页)。现在我们需要考虑进入 q A 的每个状态和退出 q A的每个状态。在这种情况下,有两个状态指向 q A,即 q init和 q Bq A指向两个状态,即 q B和 q acc。通过该算法,我们将转换 q in ->q rip ->q out替换为转换 q in ->q out,具有转换符号 Rdir +R in (R rip )*R out,其中:

  1. R dir是从 q in到 q out的原始转换
  2. R in是从 q in到 q rip的原始转换
  3. R rip是 q rip处的原始循环
  4. R out是从 q rip到 q out的原始转换

所以在这种情况下,我们将转换 q init ->q A ->q B替换为 q init ->q B和转换符号 (0+1)*1。继续这个过程,我们将总共创建 4 个新的过渡:

  1. q初始化-> q B : (0+1)*1
  2. q init -> q acc : (0+1)*
  3. q B ->q B : 0(0+1)*1
  4. q B ->q acc : 0(0+1)*

然后我们可以删除 q A

第 4 步。我们要删除 q B。同样,我们确定了 q in和 q out。这里只有一个状态进入 q B,即 q init,而离开 q B的只有一个状态,即 q acc。所以我们有:

  1. R目录= (0+1)*
  2. R in = (0+1)*1
  3. R撕裂= 0(0+1)*1
  4. 输出= 0(0+1 ) *

所以新的转换 q init ->q acc将是:

R dir +R in (R rip )*R out

(0+1)* + (0+1)*1 (0(0+1)*1)* 0(0+1)*

我们可以删除 q B

步骤 5. 由于原始 NFA 中的每个状态都已删除,因此我们完成了。所以最终的正则表达式如上所示。

请注意,最终的正则表达式可能不是最优的(在大多数情况下也不是最优的),这是算法所期望的。一般而言,为 NFA(甚至 DFA)找到最短的正则表达式非常困难(尽管对于这个示例,很容易看出第一个组件已经涵盖了所有可能的字符串)

为了完整起见,接受相同语言的最短正则表达式将是:

(0+1)*

于 2013-11-19T01:43:36.570 回答