使用状态消去法求给定有限自动机的正则表达式

问题

使用状态消去法为给定的有限自动机生成正则表达式。

解决方案

将确定性有限自动机 (DFA) 转换为正则表达式 (RE) 有两种方法。

  • Arden 定理方法。
  • 状态消去法。

给定的自动机如下所示：

步骤 1

初始状态为 A，它有一条入边。

因此，我们必须创建一个新的初始状态 qi，如下所示：

步骤 2

初始状态为 B，它有一条入边。

因此，我们必须创建一个新的最终状态 qf，如下所示：

步骤 3

现在，尝试逐个消除所有中间状态。

首先消除状态 A

从状态 qi 到 B 通过 A 有一条路径。

因此，在消除状态 A 后，我们可以连接从 qi 到 B 的直接路径，其成本为。

ε.0=0

使用状态 A 在状态 B 上有一个循环。

因此，在消除状态 A 后，我们可以绘制在状态 B 上具有成本的直接循环。

1.0=10

**消除 A 后，我们得到以下结果：**

步骤 4

现在消除状态 B

从状态 qi 到 qf 通过状态 B 有一条路径。

因此，在消除 B 后，我们可以绘制从 qi 到状态 qf 的直接路径，其成本为

0.(10)* ε=0(10)*

最终正则表达式为 = 0(10)*

更新于： 2021年6月11日

860 次查看

开启你的 职业生涯

完成课程获得认证

开始学习
广告