利用状态消除方法生成有限状态机的正则表达式

问题

给定一个有限状态机，我们需要使用状态消除方法将有限状态机转换成等效正则表达式。

第 1 步 - 初始状态 q1 有传入边。因此，创建一个新的初始状态 qi。

第 2 步 - 终止状态 q2 有传出边。因此，创建一个新的终止状态。

第 3 步 - 一个接一个地开始消除中间状态。

  • 如果有路径通过 q1 从 qi 进入 q2
  • 因此，消除 q1 之后，我们可以连接 qi 到 q2 的直接路径，该路径的成本为

    ε .c*.a=c*a

  • 使用状态 qi 在 q2 上有一个循环
  • 因此，消除状态 q1 之后，我们可以直接在状态 q2 上绘制一个成本为

    b.c*.a=b.c*.a

第 4 步

现在消除 q2。

消除 q2 之后，从状态 qi 到 qf 的直接路径具有成本。

c*a(d+bc*a)* ε=c*a(d+bc*a)*

更新于： 2021 年 6 月 11 日

2K+ 浏览

开启你的 职业生涯

完成课程获得认证

开始学习
广告