对于上述自动机，我的教科书中给出的正则表达式如下：
a*(a*ba*ba*ba*)*(a+a*ba*ba*ba*)
我无法得出这个...以下是我的尝试：
aa* + aa*(ba*ba*ba*)* + ba*ba*ba* + ba*ba*ba*(ba*ba*ba*)*
要么我错了，要么我无法将其简化为书中给出的形式。有人可以在这里指导我，指出错误或逐步向我解释吗？
我真的很感激和感激。
问问题
724 次
2 回答
2
教科书似乎是正确的。一步一步来：
一*（一*
如果正则表达式的这一部分为真（换句话说，您确实读到了“a”），您将进入状态 3。在表达式的其余部分之后：
巴*
会让你处于状态 2，
巴*
在状态 4 和
巴*
会让你回到状态 3。
现在，假设你在 'a' 期间没有读到“a” a*(a*，读下一个b会将你移动到状态 2。然后你最终会陷入与之前完全相同的情况，然后按照其余部分a*ba*ba*)，你最终会回到状态 3。
由于您现在回到状态 3，因此该部分(a*ba*ba*ba*)*可以执行任意多次，因为这与我们的第一个场景（您在 'a' 期间读取）完全相同a*(a*。
第二部分再次简单地解释了第一个场景，你必须至少阅读一个'a'，然后其余的都是一样的。
希望这会有所帮助，让我知道它是否仍然没有意义。不知道我的解释是不是太清楚了。
于 2012-01-12T19:10:18.600 回答
2
看一下这个。它提供了三种很好的算法方法来回答这些问题。如果您有时间或有兴趣，请学习其中的一个或全部三个。状态移除相当直观，虽然我喜欢 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*(r*sr*)* = r*(sr*)*。
步骤 3 是正确的，因为如果 L(s) 是 L(r) 的子集，则 r = r + s。
第 4 步是正确的，因为 r*r = rr* 和 rs + rq*s = rs + rqq*s。
第 5 步是正确的，因为 rs + r = r。
第 6 步是正确的，因为 r*s = rr*s + s。
第 7 步是正确的，因为 rs + rqq*s = rs + rq*s。
步骤 8 是正确的，因为如果 L(s) 是 L(r) 的子集，则 r = r + s。
第 9 步是正确的，因为 r*r = rr*。
请随时提出任何问题或指出我可能犯的任何错误。
EDIT2：如果您对这类问题感兴趣，请访问此链接并提交，以表达对新计算机科学 StackExchange 的热爱！！！
于 2012-01-12T19:13:11.217 回答