如何将NFA转换为正则表达式。

Question

我知道将正则表达式转换为NFA有一个算法。

但我想知道是否有一种算法可以将NFA转换为正则表达式。 如果有的话，它是什么？

如果没有，我还想知道是否所有的NFA都能转换成正则表达式。 是否存在一种NFA，正则表达式无法表示它？

谢谢！:D

- formatjam

---

一个正则表达式可以表示任何正则语言，因此对于每个可能的NFA，至少应该存在一个正则表达式。然而，我并不知道如何从NFA转换为正则表达式的算法。 - Tikhon Jelvis

而且，你的时机真的很巧合——我的朋友今天在课堂上问了我这个完全相同的问题。我当时也不记得答案了 :( - Tikhon Jelvis

在这里查看各种解答您的问题：http://cs.stackexchange.com/questions/2016/how-to-convert-finite-automata-to-regular-expressions - Masterfool

Answer 1

这是一个算法，其中每个转换都逐步替换为正则表达式，直到只剩下初始和最终状态：https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_08.pdf [PDF]。

- buzypi

---

这个是正确的，但如果节点很多就不能工作了，适用于简单和少量节点，还有其他建议吗？ - Mostafa Jamareh

我打开的链接是无效的。不过我找到了这个链接：https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_08.pdf - Justin Lessard

Answer 2

一个非确定性有限自动机可以被写成一组不等式（在Kleene代数上），每个状态对应一个变量，每个终止状态q对应一个不等式q ≥ 1，每个从状态q到状态r的转移x对应一个不等式q ≥ x r。这是一个右仿射不动点系统，在Kleene代数上，其最小不动点解为您提供了任何q的正则表达式，该正则表达式由具有q作为起始状态的NFA识别。该系统可以整理，使得给定q的所有不等式q ≥ A，q ≥ B，...，q ≥ Z合并为q ≥ A + B + ... Z。结果是一个矩阵系统≥ + H，其中是所有变量的向量，是仿射系数的向量-非终止状态为0，终止状态为1，但这些细节对接下来的内容不重要；而H是所有线性系数的矩阵。

解决右仿射系统时，逐个变量进行解决。在Kleene代数中，x ≥ a + bx的最小不动点解为x = b * a。这适用于单个和矩阵方式，因此在矩阵形式中，≥ + H的最小不动点解为= H *。

基于 Kleene 代数的矩阵形成了一个 Kleene 代数，其中矩阵加法和矩阵乘法分别用于求和和乘积运算符，而矩阵星号则用于 Kleene 星号。找到矩阵星号与解决相应的系统 ≥ + H 是同一过程。

一个通用的例子：
考虑具有状态 q、r、s 的 NFA，其中 q 是起始状态，s 是唯一的终止状态，并具有以下转换：

    a: q → q, b: q → r, c: q → s,
    d: r → q, e: r → r, f: r → s,
    g: s → q, h: s → r, i: s → s.

令 (x, y, z) = (0, 0, 1) 表示相应的仿射系数。那么，相应的右仿射系统为：

    q ≥ x + a q + b r + c s,
    r ≥ y + d q + e r + f s,
    s ≥ z + g q + h r + i s.

先解出s，得到

    s = i* (z + g q + h r) = i* z + i* g q + i* h r.

将其他不等式代入即可得到：

    q ≥ x + c i* z + (a + c i* g) q + (b + c i* h) r,
    r ≥ y + f i* z + (d + f i* g) q + (e + f i* h) r.

将此重写为

    q ≥ x' + a' q + b' r,
    r ≥ y' + d' q + e' r,

在哪里

    x' = x + c i* z, a' = a + c i* g, b' = b + c i* h,
    y' = y + f i* z, d' = d + f i* g, e' = e + f i* h.

解出 r 的值为：

    r = e'* (y' + d' q) = e'* y' + e'* d' q.

将 q 代入不等式中得到

    q ≥ (x' + b' e'* y') + (a' + b e'* d') q

并将其重写为

    q ≥ x" + a" q

在哪里

    x" = x' + b' e'* y', a" = a' + b e'* d'.

最后，解决这个问题得到 q

    q = a"* x".

这也是一般形式，体现了具有3个状态的NFA的通用故障安全解决方案。

由于q是起始状态，因此a"* x"是所寻找的正则表达式，其中a", x", a', b', d', e', x', y', x, y和z如上所示。如果您尝试内联替换它们全部，该表达式将会呈指数级增长，并且即使对于三个状态而言，其大小也会很大。

优化示例：
考虑具有q、r、s三个状态的NFA系统，其中q是起始状态，s是终止状态，转换如下：

    a: q → r, a: q → q, b: q → q, b: q → s, a: s → s, b: s → s

相应的右仿射系统为

    q ≥ a r + a q + b q
    r ≥ b s
    s ≥ 1 + a s + b s

首先解出 s：

    s ≥ 1 + a s + b s = 1 + (a + b) s ⇒ s = (a + b)*.

将r代入不等式中并求解，以找到最小的不动点：

    r ≥ b (a + b)* ⇒ r = b (a + b)*.

最后，将q代入不等式中并求解以找到最小的不动点：

    q ≥ a b (a + b)* + (a + b) q ⇒ q = (a + b)* a b (a + b)*.

生成的正则表达式是 (a + b)* a b (a + b)*。因此，通过下棋策略，可以找到更简单和更优化的解决方案形式。

- NinjaDarth