如何将有限自动机转换为正则表达式？

Question

通过标准算法，将接受相同语言的NFA转换为（最小）NFA，例如 汤普森的算法. 。但是，另一个方向似乎更加乏味，有时产生的表达是混乱的。

有哪些算法将NFA转换为同等的正则表达式？时间复杂性或结果尺寸是否有优势？

^{这应该是一个参考问题。请包括您的方法的一般替代，以及一个非平凡的示例。}

Answer 1

有几种方法可以从有限自动机转换为正则表达式。在这里，我将描述通常在学校教授的那些非常视觉的人。我相信这是实践中最常用的。但是，编写算法不是一个好主意。

状态清除方法

该算法是关于处理自动机的图，因此不太适合算法，因为它需要图形启发图，例如...状态删除。我将使用高级原语描述它。

关键主意

这个想法是在边缘上考虑正则表达式，然后删除中间状态，同时保持边缘标签一致。

主要模式可以在以下图形中看到。第一个具有$ p，q，r $的标签，即正则表达式$ e，f，g，h，i $，我们想删除$ q $。

删除后，我们组合$ e，f，g，h，i $ $（同时保留$ p $和$ r $之间的其他边缘，但这并未在此显示）：

例子

使用与在同一示例中 拉斐尔的答案:

我们依次删除$ q_2 $：

然后$ q_3 $：

然后，我们仍然必须在表达式上将星星从$ q_1 $到$ q_1 $上应用。在这种情况下，最终状态也是初始的，因此我们真的只需要添加一颗星：

$$（ab+（b+aa）（ba）^*（a+bb））^* $$

算法

L[i,j] 是该语言从$ q_i $到$ q_j $的言论。首先，我们删除了所有多重编号：

for i = 1 to n:
  for j = 1 to n:
    if i == j then:
      L[i,j] := ε
    else:
      L[i,j] := ∅
    for a in Σ:
      if trans(i, a, j):
        L[i,j] := L[i,j] + a

现在，国家撤职。假设我们要删除状态$ q_k $：

remove(k):
  for i = 1 to n:
    for j = 1 to n:
      L[i,i] += L[i,k] . star(L[k,k]) . L[k,i]
      L[j,j] += L[j,k] . star(L[k,k]) . L[k,j]
      L[i,j] += L[i,k] . star(L[k,k]) . L[k,j]
      L[j,i] += L[j,k] . star(L[k,k]) . L[k,i]

请注意，既有纸笔和算法，都应简化表达方式 star(ε)=ε, e.ε=e, ∅+e=e, ∅.e=∅ （手头您只是在不是$∅$的情况下，甚至是自循环的$ε$时，您只是不写边缘q_k $）

现在，如何使用 remove(k)？您不应轻轻删除最终状态或初始状态，否则您会错过该语言的一部分。

for i = 1 to n:
  if not(final(i)) and not(initial(i)):
    remove(i)

如果您只有一个最终状态$ q_f $和一个初始状态$ q_s $，则最终表达式是：

e := star(L[s,s]) . L[s,f] . star(L[f,s] . star(L[s,s]) . L[s,f] + L[f,f])

如果您有几个最终状态（甚至是初始状态），那么除了应用及物闭合方法之外，没有简单的方法合并这些状态。通常，这不是一个问题，但是在编写算法时，这很尴尬。更简单的解决方法是枚举所有对$（s，f）$，并在（已经是状态示例）图上运行算法，以获取所有表达式$ e_ {s，f} $，假设$ s $是唯一的初始状态$ f $是唯一的最终状态，然后进行所有$ e_ {s，f} $的结合。

这是比第一种方法更具动态化语言的事实，使其在编程时更容易容易出错。我建议使用任何其他方法。

缺点

该算法中有很多情况，例如，用于选择我们应该删除的节点，最后是最终状态的数量，最终状态也可以是初始状态。

请注意，现在算法已经编写，这很像及时的闭合方法。只有用法的上下文是不同的。我不建议实施该算法，而是使用该方法手工做到这一点是一个好主意。

Answer 2

方法

我看到的最好的方法是将自动机表示为（常规）语言的方程式系统，可以解决。它特别好，因为它似乎比其他方法产生了更多的简洁表达。

令$ a =（q， sigma， delta，q_0，f）$ an nfa，而无需$ varepsilon $ - 过渡。对于每个状态$ q_i $，创建等式

$ qquad displayStyle q_i = bigcup limits_ {q_i offeret {a} { to} q_j} aq_j co_j cup begin {cases} { varepsilon varepsilon } ， text {else} end {case} $

其中$ f $是最终状态集，$ q_i overset {a} { to} q_j $表示从$ q_i $ to $ a $标记的$ q_i $ to $ q_i $。如果您将$ cup $作为$+$或$ mid $（取决于您的正则表达式定义），则会发现这是正则表达式的方程式。

为了解决系统，您需要$ cup $和$ cdot $（字符串串联）的关联性和分配性，$ cup $和 Arden的引理¹:

令$ l，u，v subseteq sigma^*$常规语言使用$ varepsilon notin u $。然后，

美元

该解决方案是一组正则表达式$ q_i $，一个用于每个状态$ q_i $。 $ q_i $描述了以$ q_i $启动时$ a $可以接受的那些单词；因此，$ q_0 $（如果$ q_0 $是初始状态）是所需的表达式。

---

例子

^{为了清楚起见，我们用其元素来表示单例，即$ a = {a } $。该示例是由于Georg Zetzsche造成的。}

考虑这个NFA：

^[资源]

相应的方程式系统是：

美元

现在将第三个方程式插入第二个：

美元q_0 end {align} $

在最后一步，我们将Arden的引理使用$ L = Q_1 $，$ U = AB $和$ V =（B Cup AA） CDOT Q_0 $。请注意，所有三种语言都是常规的，$ varepsilon notin u = {ab } $，使我们能够应用引理。现在，我们将此结果插入第一个方程式：

美元（（A Cup BB）（AB）^*（B CUP AA） CUP BA）Q_0 CUP VAREPSILON ＆=（（A Cup BB）（AB）（AB）^*（B Cup AA）杯ba）^* qquad text {（通过Arden的引理）} end {align} $

因此，我们找到了上述自动机接受的语言的正则表达式，即

$ qquad displayStyle（（A + BB）（AB）^*（b + aa） + ba）^*。

请注意，它很简洁（与其他方法的结果相比），但并非唯一确定；求解具有不同操纵顺序的方程式系统导致其他等效！ - 表达。

---

1. 有关Arden的引理的证明，请参阅 这里.

Answer 3

Brzozowski代数法

这是与中描述的方法相同的方法 拉斐尔的答案, ，但从系统算法的角度来看，实际上是算法。事实证明，一旦您知道从哪里开始，就很容易自然地实施。同样，如果由于某种原因绘制所有自动机是不切实际的，则可以手工更容易。

在编写算法时，您必须记住，方程式必须始终是线性的，以便您对方程式有一个很好的抽象表示，即当您手工求解时可以忘记的东西。

算法的想法

我不会描述它是如何工作的，因为它做得很好 拉斐尔的答案 我建议以前阅读。取而代之的是，我专注于您在哪个顺序上解决方程式，而无需进行太多额外的计算或额外的情况。

从...开始 阿登的规则对语言方程的巧妙解决方案$ x = a^*b $ $ x =ax∪b$，我们可以将自动机视为表单的一组方程：

$$ x_i = b_i + a_ {i，1} x_1 +… + a_ {i，n} x_n $$

我们可以通过更新数组$ a_ {i，j} $和$ b_ {i，j} $相应地对$ n $解决此问题。在步骤$ n $，我们有：

$$ x_n = b_n + a_ {n，1} x_1 +… + a_ {n，n} x_n $$

Arden的规则给了我们：

$$ x_n = a_ {n，n}^*（b_n + a_ {n，1} x_1 +… + a_ + a_ {n，n，n-1} x_ {n-1}）$$

通过设置$ b'_n = a_ {n，n}^* b_n $和$ a'_ {n，i} = a_ {n，n}^* a_ {a_ {n，i} $我们得到：

$$ x_n = b'_n + a'_ {n，1} x_1 +… + a'_'_ {n，n-1} x_ {n-1} $$

然后，我们可以通过设置$ i，j来删除系统中$ x_n $的所有需求

$$ b'_i = b_i + a_ {i，n} b'_n $$ $$ $ a'_ {i，j} = a__ {i，j} + a__ {i，n} a'_ {n，j {n，j } $$

当我们解决$ x_n $时，当$ n = 1 $时，我们会获得这样的方程式：

$$ x_1 = b'_1 $$

没有$ a'_ {1，i} $。因此，我们得到了正则表达。

算法

因此，我们可以构建算法。要拥有与上述归纳相同的约定，我们会说初始状态为$ q_1 $，状态数为$ m $。首先，填充$ b $的初始化：

for i = 1 to m:
  if final(i):
    B[i] := ε
  else:
    B[i] := ∅

和$ a $：

for i = 1 to m:
  for j = 1 to m:
    for a in Σ:
      if trans(i, a, j):
        A[i,j] := a
      else:
        A[i,j] := ∅

然后解决：

for n = m decreasing to 1:
  B[n] := star(A[n,n]) . B[n]
  for j = 1 to n:
    A[n,j] := star(A[n,n]) . A[n,j];
  for i = 1 to n:
    B[i] += A[i,n] . B[n]
    for j = 1 to n:
      A[i,j] += A[i,n] . A[n,j]

最终表达是：

e := B[1]

执行

即使似乎似乎是一种对算法象征性象征性的方程式系统，该方程式也非常适合实现。 这是OCAML中此算法的实现 （断开链接）. 。请注意，除了功能 brzozowski, ，一切都要打印或用于拉斐尔的示例。请注意，简化正则表达式有一个令人惊讶的有效函数 simple_re.

Answer 4

传递闭合方法

这种方法很容易以算法的形式编写，但是会产生荒谬的较大的正则表达式，如果您手工做的话，这是不切实际的，主要是因为这太系统性了。不过，这是算法的一个好的解决方案。

关键主意

令$ r^k_ {i，j} $使用状态$ {q_1，…，q_k } $表示字符串的正则表达式。令$ n $为自动机的状态。

假设您已经知道正则表达式$ r_ {i，j} $从$ q_i $到$ q_j $，没有中间状态$ q_k $（肢体除外），均为所有$ i，j $。然后，您可以猜测添加另一个状态将如何影响新的正则表达式$ r'_ {i，j} $：仅当您直接过渡到$ q_k $时，它才会更改，并且可以这样表达：

$$ r'_ {i，j} = r_ {i，j} + r_ {i，k}。 r_ {k，k}^*。 r_ {k，j} $$

（$ r $是$ r^{k-1} $，$ r'$是$ r^k $。）

例子

我们将使用与 拉斐尔的答案. 。首先，您只能使用直接过渡。

这是第一步（请注意，带有标签$ a $的自循环会将第一个$ε$转换为$（ε+a）$。

$$ r^0 = begin {bmatrix}ε和a＆b b＆ε

在第二步中，我们可以使用$ Q_0 $（对我们而言，将其重命名为$ Q_1 $，因为$ r^0 $已经用于上述目的）。我们将看到$ r^1 $的工作方式。

从$ q_2 $到$ q_2 $：$ r^1_ {2,2} = r^0_ {2,2} + r^0_ {2,1} {r^0_ {1,1}}^* r^r^ 0_ {1,2} =ε +Bε^* a =ε + ba $。

这是为什么？这是因为只能使用$ q_1 $从$ q_2 $到$ q_2 $作为中间状态，可以通过留在这里（$ε$）或$ q_1 $（$ a $）来完成（$ε^） *$）然后回来（$ b $）。

$$ r^1 = begin {bmatrix}ε和a＆b b＆ε+ba＆a+bb a＆b+aa＆ε+ab+ab end end {bmatrix} $$

您也可以像$ r^2 $和$ r^3 $一样计算，而$ r^3_ {1,1} $将为您提供最终表达，因为$ 1 $既是初始和最终的。请注意，这里已经完成了许多表达式。否则第一个$ a $ r^0 $将为$（∅+a）$，第一个$ a $ a $ r^1 $将为$（（∅+a）+ε（ε）^*a ）$。

算法

初始化：

for i = 1 to n:
  for j = 1 to n:
    if i == j:
      R[i,j,0] := ε
    else:
      R[i,j,0] := ∅
    for a in Σ:
      if trans(i, a, j):
        R[i,j,0] := R[i,j,0] + a

及时关闭：

for k = 1 to n:
  for i = 1 to n:
    for j = 1 to n:
      R[i,j,k] := R[i,j,k-1] + R[i,k,k-1] . star(R[k,k,k-1]) . R(k,j,k-1)

然后最终表达式为（假设$ q_s $是初始状态）：

e := ∅
for i = 1 to n:
  if final(i):
    e := e + R[s,i,n]

但是您可以想象它会产生丑陋的正则表达式。您确实可以期待$（∅）^*+（a+（∅）^*）（ε）^*（a+∅）$等内容，代表与$ aa $相同的语言。请注意，简化正则表达式在实践中很有用。