5

Regex: NFA and Thompson's algorithmなどの投稿を読むと、実際には "7" や "b" などの直接文字だけでなく、

[A-Z]
[^_]
.

つまり、文字クラス (または範囲) です。したがって、私の質問 - 文字範囲を使用して NFA を構築する方法は? 「not A」、「何か他のもの」などのメタ文字を使用してから、重複する範囲を計算しますか? これにより、最終オートマトンを使用するときに、単なるテーブルではなく、ツリーのような構造を使用することになります。

更新:自明でないサイズ (>>256) のアルファベットを想定してください。

NFAについて質問していますが、後でNFAもDFAに変換したいと思っています。

4

1 に答える 1

7

最も簡単なアプローチは次のとおりです。

  1. NFA と DFA の両方で遷移のラベルとしてセグメントを使用します。たとえば、範囲 [az] は、セグメントとして表されます[97, 122]。単一文字「a」は次のようになり[97,97]ます。および任意の文字「.」となり[minCode, maxCode]ます。

  2. 否定された範囲 [^az] ごとに、開始状態から次の状態への遷移が 2 回発生します。この例では、2 つのトランジション[minCode, 96]と[123, maxCode]を作成する必要があります。

  3. 可能なすべての文字 [abcz] を列挙することによって範囲が表される場合、文字ごとの遷移を作成するか、コードで最初に文字を範囲にグループ化して遷移の数を最適化する必要があります。したがって、[abcz] は になり[a-c]|zます。したがって、4 つではなく 2 つのトランジションです。

NFA にはこれで十分です。ただし、文字範囲が交差する遷移がある場合、NFA を DFA に変換するための従来のパワー セットの構築は機能しません。この問題を解決するには、追加の一般化手順が 1 つだけ必要です。すべての入力シンボルのセットが作成されると (この場合はセグメントのセットになります)、交差しないセグメントのセットに変換する必要があります。これは時間O(n*Log(n))で実行できます。ここで、n は優先順位キュー (PQ) を使用するセット内のセグメントの数であり、セグメントは左側のコンポーネントによって順序付けられます。例：

  Procedure DISJOIN:
   Input  <- [97, 99] [97, 100] [98, 108]
   Output -> [97, 97] [98, 99], [100, 100], [101, 108]

ステップ 2.「設定状態」から新しい遷移を作成するには、アルゴリズムを次のように変更する必要があります。

   for each symbol in DISJOIN(input symbols)
     S <- empty set of symbols
     T <- empty "set state"
     for each state in "set state"
      for each transition in state.transitions
        I <- intersection(symbol, transition.label) 
        if (I is not empty)
        {
           Add I to the set S
           Add transition.To to the T
        }       

     for each segement from DISJOIN(S)
        Create transition from "set state" to T

遷移と入力記号 C を検索する際のマッチングを高速化するために、状態ごとの遷移をセグメントごとに並べ替え、二分探索を適用することができます。

于 2014-09-14T11:50:12.527 に答える