の理解（および形成）上記オートマトン、私の教科書に与えられた正規表現のために、この有限オートマトン

Question

の正規表現は、以下のとおりです。これを導出...次はそれで私の試みです：どちらか一方

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

私が間違っているか、私は与えられたフォームにそれを簡素化することができるというわけではありません 本。誰かがここで私を案内して、間違いを指摘したり、それを私にステップバイステップで説明してもらえますか？

本当にありがとうと感謝します。

Answer 1

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

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

EDIT：あなたの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：この種の質問に興味がある場合は、このリンクにアクセスしてコミットすることで、新しいコンピュータサイエンススタックエクスチェンジについていくつかの愛を示してください。

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

Answer 2

教科書が正しいようです。 （

* *

を正規表現のこの部分は（つまり、あなたが実際には「A」に読んでください）trueの場合、あなたが移動します：それはステップバイステップで撮ります

BA *

、状態2で

あなたを持つことになります。式の残りの部分に続いて状態3へ状態4で

BA *

と

*

BAは今戻った状態の3

あなたを持つことになります、あなたはしなかったと仮定a*(a*の間に 'a'を読み、次のbを読むと状態2になります。以前と全く同じ状況で終了し、残りの部分に従うことで残りの状態になります。

これで、状態3に戻ったので、(a*ba*ba*ba*)*は、必要な回数だけ実行できます。これは最初のシナリオ（a*(a*の間に 'a'を読む）と同じになります。

2番目の部分は、最初のシナリオをもう一度説明します。ここでは、少なくとも1つの「a」を読んでから残りの部分を同じにする必要があります。

希望があれば、それでも意味をなさないことを教えてください。私の説明があまりにも明確かどうかわからない。