regular-language - 如何将 DFA 转换为正则表达式？

Question

我正在阅读这本书：介绍计算理论并被困在这个例子上。

通过首先将 DFA 转换为 GNFA（广义非确定性有限自动机），然后将 GNFA 转换为正则表达式，将 DFA 转换为等效表达式。

这是示例： 在此处输入图像描述

我应该递归地使用它来到达第四个状态： 在此处输入图像描述

不幸的是，我无法理解从 b 到 c 发生了什么？我只知道我们正在尝试摆脱状态 2，但是我们如何从 b 到达 c 呢？

非常感谢！

Answer 1

将给定 DFA 转换为其正则表达式的两种流行方法是 -

1. 雅顿的方法
2. 状态消除法

雅顿定理指出：

令 P 和 Q 是 ∑ 上的两个正则表达式。

要使用 Arden 定理，必须满足以下条件 -

转换图不能有任何 ∈ 转换。必须只有一个初始状态。

步骤01：

考虑到该状态的转换，为每个状态形成一个方程。在初始状态的方程中添加“∈”。

步骤02：

以 R = Q + RP 的形式将最终状态带入，以获得所需的正则表达式。

如果 P 不包含空字符串 ∈，则 -

R = Q + RP 有一个唯一解，即 R = QP *

Answer 2

一开始这可能很棘手，但我建议您检查定义 1.64 并查看函数 CONVERT(G) 以获得更多信息。但作为对每个可能的邻居状态使用该函数的简要说明：

• 首先从a到b，添加一个start state和一个新的accept state；

• 之后需要计算 qrip 被移除后的每条新路径，在本例中为状态 1；

• 因此，从开始到 q2，您只能从 epsilon 和 a 中获得标签 a；

• 从 start 到 q3 也是如此，仅导致 b；

• 现在从 q2 到 q2 通过 qrip，你有标签 a 到 qrip 和标签 a 回来，所以你得到 (aa U b);

• 通过 qrip 到 q3 到 q3 也是如此，所以导致 bb，注意 q3 中没有循环，所以没有联合；

• 现在通过 qrip 从 q2 到 q3，您只需要连接 a 和 b 得到 ab 标签；

• 最后反过来，从 q3 到 q2 通过 qrip，连接 b 和 a，得到 ba，但这次与 q3 和 q2 之间的前一条路径合并；

• 现在选择一个新的 qrip 并再次执行相同的算法。

希望解释足够清楚，但如前所述，请参阅书中的算法以获得更好和更详细的解释。