找出给定有限自动机的正则表达式。

问题

为给定的有限自动机构造一个正则表达式。

解决方案

步骤 1 - 让我们写下方程式。

q1=q1a+ ε

q1 是起始状态，ε 将作为输入 a 添加，该输入 a 来自 q1 到 q1。

因此，我们写

状态=输入的源状态 * 输入到它的状态

步骤 2 - 同样地，

q2=q1b+q2b

q3=q2a

步骤 3 - 让我们首先简化 q1。

q1=q1a+ ε

我们可以如下重写它：

q1= ε +q1a

这类似于 R=Q+RP，其解决方案如下：

R=QP*

步骤 4 - 假设 R=q1，Q= ε，P=a

我们得到 q1 = ε.a*，因为 ε.R=R

q1=a*

步骤 5 - 将 q1 的值代入 q2 中，我们得到：

q2= q1a+q2b

=a*b+q2b

步骤 6 - 我们将此方程与 R=Q+RP 进行比较

假设 R=q2，Q=a*b，P=b

我们得到 q2=a*b.b*，因为 RR*=R+

我们将得到 q2=a*.b+

步骤 7 - 从给定的有限自动机中，如果我们想找出正则表达式，我们通常计算最终状态的方程。

由于在给定的有限自动机中，q2 是最终状态，并且 q2=a*b+

更新于： 2021年6月11日

4K+ 浏览量

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告