上記のオートマトンの場合、私の教科書で与えられている正規表現は次のとおりです。
a*(a*ba*ba*ba*)*(a+a*ba*ba*ba*)
私はこれを導き出すのに苦労しています...以下はそれに対する私の試みです：
aa* + aa*(ba*ba*ba*)* + ba*ba*ba* + ba*ba*ba*(ba*ba*ba*)*
私は間違っているか、本に記載されている形式に単純化することができません。誰かが私をここに案内してくれたり、間違いを指摘したり、段階的に説明してくれませんか？
本当にありがたいです。
これをチェックしてください。このような質問に答える 3 つの優れたアルゴリズム手法を紹介します。そのうちの 1 つ、または時間があれば 3 つすべてを学んでください。状態の除去はかなり直感的ですが、私は 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*)*
r(s+t) = rs + rt であるため、ステップ 1 は正しいです。
r*(r*sr*)* = r*(sr*)* であるため、ステップ 2 は正しいです。
L(s) が L(r) のサブセットである場合、r = r + s であるため、ステップ 3 は正しいです。
r*r = rr* および rs + rq*s = rs + rqq*s なので、ステップ 4 は正しいです。
rs + r = r であるため、ステップ 5 は正しいです。
r*s = rr*s + s なので、ステップ 6 は正しいです。
rs + rqq*s = rs + rq*s なので、ステップ 7 は正しいです。
L(s) が L(r) のサブセットである場合、r = r + s であるため、ステップ 8 は正しいです。
r*r = rr* であるため、ステップ 9 は正しいです。
ご不明な点がございましたら、お気軽にお問い合わせください。また、間違いを指摘していただくこともできます。
EDIT2: この種の質問に興味がある場合は、このリンクにアクセスしてコミットして、新しいコンピューター サイエンス StackExchange への愛を示してください!!!
教科書は正しいようです。一歩一歩：
a*(a*
正規表現のこの部分が真の場合 (つまり、実際に 'a' を読み取った場合)、状態 3 に移動します。式の残りの部分に従います。
バ*
状態 2 になります。
バ*
状態 4 および
バ*
状態 3 に戻ります。
ここで、 の間に 'a' を読まなかったと仮定するとa*(a*、次bを読むと状態 2 に移動します。その後、前とまったく同じ状況になり、残りa*ba*ba*)をたどると状態 3 に戻ります。
状態 3 に戻ったので、パーツ(a*ba*ba*ba*)*は何度でも実行できます。これは、最初のシナリオ (実行中に「a」を読み込んだ場合) と同じになるためですa*(a*。
2 番目の部分では、最初のシナリオを簡単に説明します。ここでは、少なくとも 1 つの「a」を読む必要があり、残りは同じです。
これがお役に立てば幸いです。それでも意味がない場合はお知らせください。私の説明が明確すぎるかどうかはわかりません。