4

DFAの最小化について質問があります。そのため、私は非常によく知られた手法を使用して正規表現をNFAに変換し、goto/closureアルゴリズムを使用してそれからDFAを構築しました。ここで問題は、どうすればそれを最小化できるかということです。私はここでそれについての講義を見てきました：http ：//www.youtube.com/watch？v = T9Z66NF5YRk 、そして私はまだポイントを得ることができません。DFA最小化とは何ですか？これは、IDENTICAL状態（同じ文字で同じ状態になる状態）をマージするだけですか、それとも別の状態ですか？

それで、私は次の文法から始めました：

%digit = '0'..'9'
%letter = 'a'..'z' | 'A'..'Z'
%exponent = ("e" | "E") ("+" | "-")? digit+

T_INT = digit+
T_FLOAT = T_INT exponent
T_IDENTIFIER = (letter | "$" | "_") (letter | "$" | "_" | digit)*

最終的に次のDFA（JSONとして表される）になります。

{
    "START": [{
        "type": "range",
        "from": 36,
        "to": 36,
        "shift": "1"
    }, {
        "type": "range",
        "from": 48,
        "to": 57,
        "shift": "2"
    }, {
        "type": "range",
        "from": 65,
        "to": 90,
        "shift": "1"
    }, {
        "type": "range",
        "from": 95,
        "to": 95,
        "shift": "1"
    }, {
        "type": "range",
        "from": 97,
        "to": 122,
        "shift": "1"
    }],
    "1": [{
        "type": "range",
        "from": 36,
        "to": 36,
        "shift": "1"
    }, {
        "type": "range",
        "from": 48,
        "to": 57,
        "shift": "1"
    }, {
        "type": "range",
        "from": 65,
        "to": 90,
        "shift": "1"
    }, {
        "type": "range",
        "from": 95,
        "to": 95,
        "shift": "1"
    }, {
        "type": "range",
        "from": 97,
        "to": 122,
        "shift": "1"
    }, {
        "shift": ["t_identifier"]
    }],
    "2": [{
        "type": "range",
        "from": 48,
        "to": 57,
        "shift": "2"
    }, {
        "type": "range",
        "from": 69,
        "to": 69,
        "shift": "3"
    }, {
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "3"
    }, {
        "shift": ["t_int"]
    }],
    "3": [{
        "type": "range",
        "from": 43,
        "to": 43,
        "shift": "5"
    }, {
        "type": "range",
        "from": 45,
        "to": 45,
        "shift": "5"
    }, {
        "type": "range",
        "from": 48,
        "to": 57,
        "shift": "4"
    }],
    "4": [{
        "type": "range",
        "from": 48,
        "to": 57,
        "shift": "4"
    }, {
        "shift": ["t_float"]
    }],
    "5": [{
        "type": "range",
        "from": 48,
        "to": 57,
        "shift": "4"
    }]
}

では、どうすれば最小化できますか？

アップデート：

さて、これが私のアルゴリズムです。次のDFAが与えられます：

{
    0: [{
        from: 97,
        to: 97,
        shift: 1
    }],
    1: [{
        from: 97,
        to: 97,
        shift: 3
    }, {
        from: 98,
        to: 98,
        shift: 2
    }],
    2: [{
        from: 98,
        to: 98,
        shift: 4
    }],
    3: [{
        from: 97,
        to: 97,
        shift: 3
    }, {
        from: 98,
        to: 98,
        shift: 4
    }],
    4: [{
        from: 98,
        to: 98,
        shift: 4
    }]
}

これは私がそれを最小化するために行うことです：

  1. 各状態（私の例では0、1、2、3、4として番号が付けられています）について、そのような状態を識別する一意のハッシュを取得します（たとえば、state0の場合、これはfrom = 97、to = 97、shift = 1、state1の場合はthis from = 97、to = 97、shift = 3＆from = 98、to = 98、shift = 2などになります…）

  2. 得られたハッシュを比較し、2つの同一のハッシュが見つかった場合は、それをマージします。私の例では、state2ハッシュはfrom = 98＆shift = 4＆to = 98になり、state4ハッシュはfrom = 98＆shift = 4＆to = 98になります。これらは同じなので、新しいstate5にマージできます。その後、DFAはこんな風に見える：

    {
0: [{
    from: 97,
    to: 97,
    shift: 1
}],
1: [{
    from: 97,
    to: 97,
    shift: 3
}, {
    from: 98,
    to: 98,
    shift: 5
}],
3: [{
    from: 97,
    to: 97,
    shift: 3
}, {
    from: 98,
    to: 98,
    shift: 5
}],
5: [{
    from: 98,
    to: 98,
    shift: 5
}]

    }

  3. 変更がなくなるまでこれを続けます。次のステップ（状態1と3をマージ）はDFAを次の形式に変換します。

    {
0: [{
    from: 97,
    to: 97,
    shift: 6
}],
6: [{
    from: 97,
    to: 97,
    shift: 6
}, {
    from: 98,
    to: 98,
    shift: 5
}],
5: [{
    from: 98,
    to: 98,
    shift: 5
}]

    }

  4. 同一の状態はもうありません。つまり、完了です。

2回目の更新：

さて、次の正規表現が与えられます：'a'（'ce'）*（'d' |'xa' |'AFe'）+ | 'b'（'ce'）*（'d' |'xa' |'AFe'）+'ce' +次のDFAがあります（START->開始状態、["accept"]-> so to受け入れ状態への移行と言います）：

{
    "START": [{
        "type": "range",
        "from": 98,
        "to": 98,
        "shift": "1.2"
    }, {
        "type": "range",
        "from": 97,
        "to": 97,
        "shift": "17.18"
    }],
    "1.2": [{
        "type": "range",
        "from": 120,
        "to": 120,
        "shift": "10"
    }, {
        "type": "range",
        "from": 100,
        "to": 100,
        "shift": "6.7"
    }, {
        "type": "range",
        "from": 65,
        "to": 65,
        "shift": "8"
    }, {
        "type": "range",
        "from": 99,
        "to": 99,
        "shift": "4"
    }],
    "10": [{
        "type": "range",
        "from": 97,
        "to": 97,
        "shift": "6.7"
    }],
    "6.7": [{
        "type": "range",
        "from": 99,
        "to": 99,
        "shift": "15"
    }, {
        "type": "range",
        "from": 120,
        "to": 120,
        "shift": "13"
    }, {
        "type": "range",
        "from": 100,
        "to": 100,
        "shift": "6.7"
    }, {
        "type": "range",
        "from": 65,
        "to": 65,
        "shift": "11"
    }],
    "15": [{
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "14.accept"
    }],
    "14.accept": [{
        "type": "range",
        "from": 99,
        "to": 99,
        "shift": "16"
    }, {
        "shift": ["accept"]
    }],
    "16": [{
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "14.accept"
    }],
    "13": [{
        "type": "range",
        "from": 97,
        "to": 97,
        "shift": "6.7"
    }],
    "11": [{
        "type": "range",
        "from": 70,
        "to": 70,
        "shift": "12"
    }],
    "12": [{
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "6.7"
    }],
    "8": [{
        "type": "range",
        "from": 70,
        "to": 70,
        "shift": "9"
    }],
    "9": [{
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "6.7"
    }],
    "4": [{
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "2.3"
    }],
    "2.3": [{
        "type": "range",
        "from": 120,
        "to": 120,
        "shift": "10"
    }, {
        "type": "range",
        "from": 100,
        "to": 100,
        "shift": "6.7"
    }, {
        "type": "range",
        "from": 65,
        "to": 65,
        "shift": "8"
    }, {
        "type": "range",
        "from": 99,
        "to": 99,
        "shift": "5"
    }],
    "5": [{
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "2.3"
    }],
    "17.18": [{
        "type": "range",
        "from": 120,
        "to": 120,
        "shift": "25"
    }, {
        "type": "range",
        "from": 100,
        "to": 100,
        "shift": "22.accept"
    }, {
        "type": "range",
        "from": 65,
        "to": 65,
        "shift": "23"
    }, {
        "type": "range",
        "from": 99,
        "to": 99,
        "shift": "20"
    }],
    "25": [{
        "type": "range",
        "from": 97,
        "to": 97,
        "shift": "22.accept"
    }],
    "22.accept": [{
        "type": "range",
        "from": 120,
        "to": 120,
        "shift": "28"
    }, {
        "type": "range",
        "from": 100,
        "to": 100,
        "shift": "22.accept"
    }, {
        "type": "range",
        "from": 65,
        "to": 65,
        "shift": "26"
    }, {
        "shift": ["accept"]
    }],
    "28": [{
        "type": "range",
        "from": 97,
        "to": 97,
        "shift": "22.accept"
    }],
    "26": [{
        "type": "range",
        "from": 70,
        "to": 70,
        "shift": "27"
    }],
    "27": [{
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "22.accept"
    }],
    "23": [{
        "type": "range",
        "from": 70,
        "to": 70,
        "shift": "24"
    }],
    "24": [{
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "22.accept"
    }],
    "20": [{
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "18.19"
    }],
    "18.19": [{
        "type": "range",
        "from": 120,
        "to": 120,
        "shift": "25"
    }, {
        "type": "range",
        "from": 100,
        "to": 100,
        "shift": "22.accept"
    }, {
        "type": "range",
        "from": 65,
        "to": 65,
        "shift": "23"
    }, {
        "type": "range",
        "from": 99,
        "to": 99,
        "shift": "21"
    }],
    "21": [{
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "18.19"
    }]
}

話は同じですが、どうすれば最小化できますか？古典的なHopcroftのアルゴリズムに従って、このすべてのテーブル構造を使用し、区別できない状態を判別し、それらをマージするなどの場合、15の状態を含むDFAを取得します（このツールを使用してください：http：//regexvisualizer.apphb.com/この正規表現a（ce）（d | xa | AFe）+ | b（ce）（d | xa | AFe）+ ce +を使用して確認します）。Hopcroftのアルゴリズムを使用して縮小した後のDFAは次のようになります。

Hopcroftの最小化されたDFA

私が思いついたアルゴリズムは、Hopcroftのアルゴリズムを「再考」した後、上に表示されているものよりも小さいDFAを構築します（画質については申し訳ありませんが、なぜ小さいのかを理解するために段階的に再描画する必要がありました）。

私のアルゴリズム

そして、これがどのように機能するかです。「状態の同等性」に関する決定は、状態が与えられたハッシュ関数の結果に基づいています（たとえば、「START」）。その状態から開始すると、DFAから構築できる短い文字列が作成されます。 。上記のDFAとSTART状態が与えられると、次の文字列を作成できます：98-> 120、98-> 100、98-> 65、98-> 99、97-> 120、97-> 100、97-> 65 、97-> 99なので、START状態のハッシュ関数の結果とします。DFAの各状態に対してこの関数を実行すると、一部の状態でこの関数が同じ結果（ "1.2"、 "6.7"、 "2.3" AND "10"、 "13" AND"15"を与えることがわかります。 、"16" AND "11"、 "8"、 "26"、 "23" AND "12"、 "9"、 "4"、

どこかで間違っていることがわかりますが、アルゴリズムによって生成された最小化されたDFAの何が問題になっているのかわかりませんか？

4

3 に答える 3

5

提案されたアルゴリズムは、同じように動作する複雑な構造を検出しないため、完全な最小化を行いません。このDFA（JFLAPによって描画された）を見てこれを理解するには：

ここに画像の説明を入力してください

最小化はq1とq2を組み合わせますが、概説されたアルゴリズムはうまくいきません。

これとは対照的に、Hopcroftのアルゴリズムは最初は次のように分割します。

   {q0, q1, q2}, {q3}

次に、q0にはq3への遷移がないため、最初のセットを分割します。

   {q0}, {q1, q2}, {q3}

q1とq2は同じように動作するため、さらに分割することはありません。

于 2012-06-21T11:32:54.853 に答える
4

元のDFAをM1と呼びます。簡単に言えば、最小化されたDFA（M2と呼びます）を構築することは、最小数の状態を含むDFAに変換することを意味します。したがって、M2の状態の数は、M1の状態の数よりも少なくなります。ここで注意すべき重要な点は、M1とM2は同等である必要があるということです。つまり、これらは同じ正規言語を定義する必要があります。最小化されたDFAを構築するには、同一の状態を探すだけでなく、次のことも必要です。

  1. 「到達不能」状態の削除：
    これには、入力文字列について、DFAの初期状態から到達不可能な状態を削除することが含まれます。

  2. 「デッド」または「トラップ」状態の削除：
    これには、それ自体で終了する非受け入れ状態の削除が含まれます。それらはTRAP状態とも呼ばれます。

  3. 「区別できない」状態の削除：
    これには、入力文字列で互いに区別できない状態を削除することが含まれます。

DFAの最小化に使用される一般的なアルゴリズムもいくつかあります。

これらのアルゴリズムを実行することは価値があるかもしれません！

于 2012-06-21T09:14:23.663 に答える
1

NFAをDFAに決定するコードがある場合、それを最小化するための最も簡単なソリューションは、Brzozowskiのアルゴリズムです。NFAを逆にする関数を実装する必要がありますが、これはかなり簡単です。（遷移を逆にし、開始状態を交換し、状態を受け入れます）

決定および逆関数を取得すると、Brzozowskiの最小化は次のように実装されます。

minimize(nfa) = determinize(reverse(determinize(reverse(nfa))))

私見、これは非常にエレガントなソリューションです

于 2013-06-26T19:40:22.183 に答える