从 dfa 转换为正则表达式

Question

有人可以向我解释一下如何将此 DFA 转换为正则表达式吗？

我尝试过使用 Arden 定理，但我不知道如何简化方程以获得此 DFA 的正则表达式。如果有人可以告诉我如何简化表达式，那将是一个很大的帮助。

Answer 1

首先，让我们将各州命名为𝑞_𝑎...𝑞_𝑓，如下所示：

这些状态代表从起始状态𝑞_𝑎开始时导致该状态的表达式，因此我们寻找的解决方案是𝑞_end = 𝑞_𝑑 + 𝑞_𝑓

然后根据其他状态创建每个状态的方程：

      𝑞_𝑎 = ε
𝑞_𝑏 = (𝑞_𝑎 + 𝑞_𝑐)1
𝑞_𝑐 = 𝑞_𝑏2
𝑞_𝑑 = (𝑞_𝑎 + 𝑞_𝑐 + 𝑞_𝑑)(3 + 4)
𝑞_𝑒 = (𝑞_𝑑 + 𝑞_𝑓)5
𝑞_𝑓 = 𝑞_𝑒（6 + 7）
𝑞_结束 = 𝑞_𝑑 + 𝑞_𝑓

我们可以替换 𝑞_𝑎、𝑞_𝑐 和 𝑞_𝑓:

      𝑞_𝑏 = (ε + 𝑞_𝑏2)1 = 1 + 𝑞_𝑏21
𝑞_𝑑 = (ε + 𝑞_𝑏2 + 𝑞_𝑑)(3 + 4) = (ε + 𝑞_𝑏2)(3 + 4) + 𝑞 _𝑑(3 + 4)
𝑞_𝑓 = (𝑞_𝑑 + 𝑞_𝑓)5(6 + 7) = 𝑞_𝑑5(6 + 7) + 𝑞_𝑓 5（ 6 + 7)
𝑞_结束 = 𝑞_𝑑 + 𝑞_𝑓

我们可以将雅顿定理应用于其中的每一个：

      𝑞_𝑏 = 1(21)*
𝑞_𝑑 = (ε + 𝑞_𝑏2)(3 + 4)(3 + 4)*
𝑞_𝑓 = (𝑞_𝑑56 + 𝑞_𝑑57)(5(6 + 7))*
𝑞_结束 = 𝑞_𝑑 + 𝑞_𝑓

我们可以替代𝑞_𝑏:

      𝑞_𝑑 = (ε + 1(21)*2)(3 + 4)(3 + 4)* = (12)*(3 + 4)(3 + 4)*
𝑞_𝑓 = 𝑞_𝑑5(6 + 7)(5(6 + 7))*
𝑞_结束 = 𝑞_𝑑 + 𝑞_𝑓

和𝑞_𝑑和𝑞_𝑓：

      𝑞_𝑑 = (12)*(3 + 4)(3 + 4)*
𝑞_𝑓 = (12)*(3 + 4)(3 + 4)*5(6 + 7)(5(6 + 7))*

解决方案：

      𝑞_结束 = (12)*(3 + 4)(3 + 4)*(ε + 5(6 + 7)(5(6 + 7))*)
= (12)*(3 + 4)(3 + 4)*(5(6 + 7))*

---

注意：如果我们将其写为编程中使用的正则表达式，那么 𝑞_end 可以写为：

^(12)*[34]+(5[67])*$