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

Question

对于上面的自动机，我的教科书中给出的正则表达式如下：

a*(a*ba*ba*ba*)*(a+a*ba*ba*ba*)

我在推导这个时遇到困难...以下是我的尝试：

aa* + aa*(ba*ba*ba*)* + ba*ba*ba* + ba*ba*ba*(ba*ba*ba*)*

要么我错了，要么我无法将其简化为书中给出的形式。有人可以在这里指导我，指出错误或逐步向我解释吗？

我真的非常感谢并欣赏这一点。

Answer 1

看看这个。它提供了三种很好的算法方法来回答此类问题。如果您有时间或兴趣，可以学习其中之一，或者全部三个。状态移除相当直观，尽管我喜欢 Kleene 的传递闭包方法。

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

编辑：您的 RE 与所提供的相同。这是他们的减少到你的：

0. a*(a*ba*ba*ba*)*(a+a*ba*ba*ba*)

1. = a*(a*ba*ba*ba*)*a + a*(a*ba*ba*ba*)*a*ba*ba*ba*

2. = a*(ba*ba*ba*)*a + a*(ba*ba*ba*)*ba*ba*ba*

3. = a*a + a*(ba*ba*ba*)*a + a*(ba*ba*ba*)*ba*ba*ba*

4. = aa* + a*(ba*ba*ba*)*ba*ba*ba*a + a*(ba*ba*ba*)*ba*ba*ba*

5. = aa* + a*(ba*ba*ba*)*ba*ba*ba*

6. = aa* + aa*(ba*ba*ba*)*ba*ba*ba* + (ba*ba*ba*)*ba*ba*ba*

7. = aa* + aa*(ba*ba*ba*)* + (ba*ba*ba*)*ba*ba*ba*

8. = aa* + aa*(ba*ba*ba*)* + ba*ba*ba* + (ba*ba*ba*)*ba*ba*ba*

9. = aa* + aa*(ba*ba*ba*)* + ba*ba*ba* + ba*ba*ba*(ba*ba*ba*)*

步骤 1 是正确的，因为 r(s+t) = rs + rt。

步骤 2 是正确的，因为 r*(rsr)* = r*(sr*)*。

如果 L(s) 是 L(r) 的子集，则步骤 3 是正确的，因为 r = r + s。

步骤 4 是正确的，因为 rr = rr 且 rs + rqs = rs + rqqs。

第 5 步是正确的，因为 rs + r = r。

步骤 6 是正确的，因为 rs = rrs + s。

步骤 7 是正确的，因为 rs + rqqs = rs + rqs。

如果 L(s) 是 L(r) 的子集，则步骤 8 是正确的，因为 r = r + s。

步骤 9 是正确的，因为 rr = rr。

请随时提出任何问题或指出我可能犯的任何错误。

Answer 2

教科书看起来是正确的。一步一步来：

一个*（一个*

如果正则表达式的这一部分为真（换句话说，您确实读入了“a”），您将进入状态 3。跟随表达式的其余部分：

巴*

会让你处于状态2，

巴*

在状态 4 和

巴*

会让你回到状态3。

现在，假设您在

a*(a*

期间没有读到“a”，阅读下一个

b

将使您进入状态2。然后您最终会遇到与之前完全相同的情况，并遵循其余的

 a*ba*ba*)

你最终回到状态 3。

由于您现在回到状态 3，因此

(a*ba*ba*ba*)*

部分可以执行任意多次，因为这与我们的第一个场景相同（您在

a*(a*

期间读入“a”）。

第二部分简单地再次解释了第一个场景，你必须读至少一个“a”，然后其余的都是一样的。

希望这有帮助，如果仍然没有意义，请告诉我。不知道我的解释是否太清楚了。