finite-automata - Brzozowski 代数方法在该 FA 上的应用

Question

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

Understanding (and forming) the regular expression of this finite automaton

感谢用户 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

Answer 1

我会尝试一下...我们首先减少每个等式，以便我们没有任何 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*

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