5

このウェブサイトで同じ質問を見つけました。その答えは、NFA を正規表現に変換する方法を説明した PDFでした。ただし、この方法にはいくつかの条件があるため、これは機能しません。

  1. 初期状態から他のすべての状態への遷移があり、初期状態への遷移はありません。
  2. 入ってくる遷移のみを持つ (出て行く遷移がない) 単一の受け入れ状態があります。
  3. 受け入れ状態は、初期状態とは異なります。
  4. 初期状態と受け入れ状態を除いて、他のすべての状態は遷移を介して他のすべての状態に接続されます。特に、各状態にはそれ自体への遷移があります。

そして、私の例では、開始状態は次の状態に行くだけで、すべての状態に行くわけではなく (たとえば、q0 は q1 に行くが、q2、q3 には行かない)、開始状態への遷移があります。

では、NFA を正規表現に変換する最も簡単な方法は何でしょうか? 開始状態がすべての状態に接続されていないこの種の DFA に出くわしたため、具体的なものがないため、NFA の例を挙げていません。これは一般的な質問です。開始状態。

この種の NFA を変換する一般的なアルゴリズムが必要です。

4

1 に答える 1

4

答えは、これらの条件に合わせて NFA を変更できるため、これらの条件を想定することです。

どのような種類の NFA でも、元の初期状態へのイプシロン遷移を持つ新しい初期状態 q 0を追加できます。また、∅ と呼ばれる追加の遷移記号を使用することもできます (彼らはそれを空集合記号と呼び、元の NFA のどのシンボルとも一致しない) それから他の状態への場合、この新しい状態を新しい初期状態として使用します。これは、元の NFA で受け入れられている言語を変更しないことに注意してください。これにより、NFA は最初の条件を満たします。

どのような種類の NFA でも、元の NFA のすべての受け入れ状態からのイプシロン遷移を持つ新しい受け入れ状態 q aを追加できます。次に、これを唯一の受け入れ状態としてマークします。これは、元の NFA で受け入れられている言語を変更しないことに注意してください。これにより、NFA は 2 番目の条件を満たします。

以上の構成により、q 0 != q aとすることで、第3の条件を満たします。

そして、あなたが提供したリンクでは、元のNFAの実際のアルファベットが一致しない∅（空集合記号）と呼ばれる特別な遷移記号を持つことによって、4番目の条件が説明されています. したがって、この新しいシンボルを使用して、すべての状態から他の状態への遷移を追加できます。これは、元の NFA で受け入れられている言語を変更しないことに注意してください。

これで、NFA は 4 つの要件を満たすように変更されました。そこでアルゴリズムを適用して、元の NFA と同じ言語を受け入れる正規表現に NFA を変換できます。

さらに質問に答えるために編集します：

コメントであなたの質問に答えるために、q Aと q Bの 2 つの状態を持つ NFA を考えてみましょう。q Aは初期状態であり、唯一の受け入れ状態です。記号 0,1 でq Aからそれ自体への遷移があります。また、シンボル 1 で q Aからq Bへの遷移があります。最後に、シンボル 0 でq Bから q Aへの遷移があります。

視覚化：

0,1    
  | | 1
->q A ----->q B
  ^ |
  |------|
     0

ステップ 2. NFA を正規化するときは、 q Aを指す新しい初期状態 (q init ) を置き、q Aからの新しい受け入れ状態 (q acc )を置きます。

ステップ 3. q Aを削除します。したがって、q Aはアルゴリズムの q ripです (3 ページ)。ここで、q Aに入るすべての状態と q Aから出るすべての状態を考慮する必要があります。この場合、q Aを指す 2 つの状態、つまり q initと q Bがあります。q Aが指し示す状態には、q Bと q accの 2 つがあります。アルゴリズムによって、遷移 q in ->q rip ->q outを遷移記号 R を持つ遷移 q in ->q outに置き換えます。dir +R in (R rip )*R out、ここで:

  1. R dirは、q inから q outへの元の遷移です。
  2. R inは、q inから q ripへの元の遷移です。
  3. R ripは q ripでの元のループです
  4. R outは、q ripから q outへの元の遷移です。

したがって、この場合、遷移 q init ->q A ->q Bを q init ->q Bで遷移記号 (0+1)*1 に置き換えます。このプロセスを続けて、合計 4 つの新しいトランジションを作成します。

  1. q init ->q B : (0+1)*1
  2. q init ->q acc : (0+1)*
  3. q B ->q B : 0(0+1)*1
  4. q B ->q acc : 0(0+1)*

次に、q Aを削除できます。

ステップ 4. q Bを削除します。ここでも、q inと q outを識別します。ここでq Bに到達する状態は q initであり、q Bから離れる状態は q accである 1 つだけです。したがって、次のようになります。

  1. R dir = (0+1)*
  2. R in = (0+1)*1
  3. Rリップ= 0(0+1)*1
  4. Rアウト= 0(0+1)*

したがって、新しい遷移 q init ->q accは次のようになります。

R dir + R in (R rip )*R out

(0+1)* + (0+1)*1 (0(0+1)*1)* 0(0+1)*

そして q Bを取り除くことができます。

ステップ 5. 元の NFA のすべての状態が削除されたので、これで完了です。したがって、最終的な正規表現は上に示されています。

最終的な正規表現は最適ではない可能性があることに注意してください (ほとんどの場合、最適ではありません)。これはアルゴリズムから予想されます。一般に、NFA (または DFA でさえ) の最短の正規表現を見つけることは非常に困難です (ただし、この例では、最初のコンポーネントがすべての可能な文字列を既にカバーしていることは簡単にわかります)。

完全を期すために、同じ言語を受け入れる最短の正規表現は次のようになります。

(0+1)*

于 2013-11-19T01:43:36.570 に答える