regex - NFAからREKleeneの定理へ

Question

これが私のNFAです。

これが私の試みです。

• 新しい開始ノードと最終ノードを作成します
• 次に、左から2番目のノードを削除します。
• 次に、右から2番目のノードを削除します。これによりab*aが得られます。
• 次に、左から2番目のノードを削除します。これによりabb*bが得られます。
• 次に、右から2番目のノードを削除します。これによりb + ab*aが得られます。

これはabbb （b + ab a）*につながります

これは正解ですか？

Answer 1

いいえ、あなたは正しくありません:(

_{開始状態を作成する必要はありません。-符号付きの最初の状態は開始状態です。また、a,bラベルはaorを意味しますbが、そうではありませんab}

_{Arden の定理と呼ばれる定理があり、NFA を RE に変換するのに非常に役立ちます。}

この NFA の正規表現とは?

NFADFA の最初の部分 :

ステップ1：

(-) --a,b-->(1)   

(a+b) を意味します

step-2:次に stat 1 から 2 へ。state 2 は状態 final を受け入れていることに注意してください (符号+あり)。

(1) --b--->(2+)

(a+b)bしたがって、最終状態に到達する 必要があります 。

step-3:最終状態2の1人、何b人でも受け付けます(任意の数は1つ以上を意味します)。これは2、ラベルの状態での自己ループが原因ですb。

したがって、b*状態 2 で受け入れられます。

ステップ-4:

実際には に 2 つのループがありますstate-2。

• 1 つは、ステップ 3bで説明したように、ラベル付きの自己ループです。その表現はb*

• 状態 2 の 2 番目のループは状態 3 経由です。
  状態 2 の 2 番目のループの式はaa*b
  、なぜ式aa*b?

  なぜなら：

            a-  
            ||               ====>  aa*b
            ▼|   
  (2+)--a-->(3) --b-->(2+)   
  

bしたがって、ステップ 3 とステップ 4 では、状態 2 のループのため、ラベル付きまたはaa*b===> 経由でループバックできます。(b + aa*b)*

したがって、NFA の正規表現は次のとおりです。

(a+b) b (b + aa*b)*