この有限オートマトンの正規表現を理解（および形成）

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

これをチェックしてください。これは、このような質問に答えるための3つの良好なアルゴリズム方法を示しています。時間や傾向がある場合は、そのうちの1つまたは3つすべてを学びます。私はクリーンの推移的閉鎖法が好きですが、状態の除去はかなり直感的です。

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*）*から正しいです。

l（s）がl（r）のサブセットである場合、r = r + sなので、ステップ3は正しいです。

ステップ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なので正しいです。

l（s）がl（r）のサブセットである場合、r = r + sなので、ステップ8は正しいです。

ステップ9は、r*r = rr*なので正しいです。

質問をしたり、私が犯したかもしれない間違いを指摘してください。

edit2：これらの種類の質問に興味がある場合は、このリンクに行ってコミットして、新しいコンピューターサイエンスstackexchangeに対する愛を示してください!!!

http://area51.stackexchange.com/proposals/35636/computer-science-non-programming？referrer = rpnxa1_2bnyzxn85c5cqq2

Answer 2

教科書は正しいようです。段階的にそれを取る：

a*（a*

正規表現のこの部分が真である場合（言い換えれば、実際に「A」で読んでいます）、あなたは状態3に移動します。

ba*

州2にあなたを持っていますか

ba*

状態4および

ba*

州3に戻ってきます。

さて、あなたが「a」で読んでいなかったと仮定します a*(a*, 、次を読んでいます b 2に移動します2。あなたは以前とまったく同じ状況になり、残りをフォローすることで終わります a*ba*ba*) あなたは状態3に戻ってしまいます。

あなたは今ステート3に戻っているので、その部分 (a*ba*ba*ba*)* これは私たちの最初のシナリオと同じであるため、何度も必要なだけ実行できます（中に「A」で読む場所 a*(a*).

2番目の部分では、最初のシナリオを再度説明します。ここでは、少なくとも1つの「A」を読む必要があり、残りは同じです。

これが役立つことを願っています、それがまだ意味をなさない場合、私に知らせてください。私の説明があまりにも明確であるかどうかはわかりません。