1

私は明日の試験のために勉強していて、NFA を Regex に変換する方法を説明する多くのチュートリアルをチェックしましたが、自分の答えを確認できないようです。チュートリアルに従って、そのNFAを解決しました

ここに画像の説明を入力

私の解決策は次のとおりです。

あば_

私は正しいですか？

4

2 に答える 2

2

NFA を正規表現に変換するには?

あなたの答えa*ba*は正解です。NFA次のように、特定の画像 から回答を得ることができます。

  • ラベルの開始状態 q 0aに自己ループがあります。そのため、RE のanull を含め、初期 (プレフィックス) で任意の数のs が可能です。^したがって、正規表現 (RE) は で始まりa*ます。

  • b最終状態に到達するために必要なのは 1 つだけです。実際には受け入れ文字列の場合。およびbの文字列に少なくとも 1 つ存在する必要があります。したがって、REは q 1または q 2のいずれかに到達します。どちらも最終状態です。 aba*b

  • 最終状態 (q 1または q 2 )に達したら。文字列には他にありません( from q 1と q 2bの出力エッジはありません)。b

  • q 1と q 2ではシンボル is のみaが可能です。また、q 1または q 2で、q 1と q 2の間の移動スイッチがあり、両方が最終的です。そのため、symbol の後に任意の数のs をサフィックスに含めることができます。(したがって、文字列は で終わります)。 abaa*

RE はa*ba*です。

また、そのDFAは次のとおりです。 

 DFA: 
======

    a-          a-  
    ||          ||
    ▼|          ▼|
--►(q0)---b---►((q1))      

    a*    b      a*    :RE  
                       ====

  • の任意の数は次aのq0とおりです。 a*

  • 取得しbたら、最終状態に切り替えることができますq1: b

  • 最終状態では、いくつでもa可能です: a*

そして、最小化されたDFAです！

FAsとに関する私による興味深い回答を次に示しREsます。役に立つと思います。

  1. DFA の正規表現の書き方
  2. RE から DFA へ
  3. DFA への正規表現
  4. 正規表現から同等の正規文法を構築する
  5. 文脈自由文法で左再帰をなくす方法
  6. a* は (a*)* と同じですか?
  7. 正規表現のコンテキスト: は(AB)* = A*B*?
于 2013-01-12T10:11:53.560 に答える
1

次の両方が当てはまるという点で、その答えは正しいです。

  • 正規表現に一致するすべての文字列により、NFA が受け入れ状態 (二重丸で囲まれた状態) で終了します。
  • NFA を受け入れ状態で終了させる文字列も、正規表現に一致します。

ただし、あなたが投稿していないため、あなたの作品を確認できません。

于 2013-01-11T22:02:24.463 に答える