早些时候，我在这里提出了一个问题，寻求将有限自动机的转换图转换为正则表达式的帮助:
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
最佳答案
我会尝试一下...我们首先减少每个方程，这样我们就不会有任何 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*
这看起来是正确的，因此我们可以将其转换为您的。你应该尝试这个练习。
关于finite-automata - Brzozowski 代数方法在此 FA 上的应用，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8861454/