2

早些时候，我在这里问了一个问题，寻求将有限自动机的转移图转换为正则表达式的帮助：

理解（并形成）这个有限自动机的正则表达式

感谢用户 Patrick87，我能够找到我正在寻找的帮助。我还阅读了他在回答中提到的以下链接：

http://krchowdhary.com/toc/dfa-to-reg-exp.pdf

它解释了三种查找正则表达式的算法方法。直觉上，我被 Brzozowski 代数方法所吸引，并试图解决我在上一篇文章中寻求帮助的 FA，该问题在顶部提到。

以下是我为FA制作的特征方程。如果我错了，请告诉我并纠正我，并指出我正确的方向！

R1 = bR2 + aR3

R2 = aR2 + bR4

R3 = aR3 + bR2 + λ

R4 = aR4 + bR3

这些是正确的吗？如果是，那么我该如何进行替换，因为每个 Ri 都将根据 Rj 来表示，其中 i≠j。

请帮忙 :D

4

1 回答 1

3

我会尝试一下...我们首先减少每个方程，这样我们就没有任何 Ri 等于包含它们自己的表达式...

R1 = bR2 + aR3
R2 = a*bR4
R3 = a*bR2 + a*
R4 = a*bR3

现在换人...首先消除R4

R2 = a*ba*bR3

现在我们摆脱 R2

R1 = ba*ba*bR3 + aR3
R3 = a*ba*ba*bR3 + a*

我们不希望 R3 在其自己的 RHS 上...

R3 = (a*ba*ba*b)*a*

现在消除R3

 R1 = ba*ba*b(a*ba*ba*b)*a* + a(a*ba*ba*b)*a*

这看起来不错，因此我们可以将其转换为您的。你应该试试这个练习。

于 2012-01-14T14:30:05.273 回答