c++ - DFA 最小化 Brzozowski アルゴリズム

Question

DFA を最小化するために Brzozowski のアルゴリズムを実装しようとしています。以下は同じアルゴリズムです。

DFA = d(r(d(r(NFA)))) 

ここでr()は NFA の反転であり、D()NFA を DFA に変換します。

r()しかし、Googleで検索してもあまり情報が得られないという意味がわかりません。

誰でもr()NFAとは何か説明してもらえますか?

利用可能な他の単純なアルゴリズムまたは C++ 実装があれば、リンクを教えてください。

Answer 1

これは OpenFst からの実装です。

この論文には、逆演算を適用した結果を示す図 (15 ページ) があります。

FSM の操作を理解するのに役立つ簡単な方法は、OpenFst のようなライブラリを使用してマシンを作成および操作し、Graphviz を使用して結果を視覚化することです。

Answer 2

reverse.c のコード (ここにありますが、現在は機能していません) にコメントがあります/* Create reversed edges */。r()つまり、すべてのエッジの方向を反転していると言えます (さらに、反転したオートマトンの開始状態が明確に定義されていることを確認します)。

Answer 3

Brzozowski のアルゴリズム

Brzozowski のアルゴリズムは、次のように書くとより明確になります。

minimized_DFA = subset(reverse(subset(reverse(NFA))))

ここで、subsetはサブセットの構築 (パワーセットの構築とも呼ばれます) を示します。サブセットの構築では、NFA 内の (イプシロン遷移による) 等価な状態セットごとにすべての遷移をシミュレートすることにより、DFA を構築します。

NFA を元に戻すには、次の手順が必要です。

1. NFA のすべての遷移エッジの方向を逆にします。
2. NFA のすべての受け入れ状態へのイプシロン遷移を持つ新しい開始状態を作成します。
3. NFA ですべての受け入れ状態を非受け入れとしてマークします。
4. 古い開始状態を新しい受け入れ状態にします。

ステップ 2 から 4 は、受け入れ状態と開始状態の役割を効果的に交換します。

---

Brzozowski のアルゴリズムの例

これは、コンパイラ コースのUdacity クイズに基づいて DFA を最小化する例です(手順は、初期入力としての NFA と同じです)。

最初の DFA:

この DFA は、 のような文字列を受け入れ、 のような文字列{"", "a", "aa", "aaa", "aaabba", "ba", "bab", "ababa", "ababb"}を拒否します{"b", "ab", "aab", "aabb", "bb", "bbb"}。つまり、部分文字列"b"も含まれていない限り、 a を持つ文字列は拒否されます"ba"。s1-s3とs2-s4が冗長であることは明らかです。

ステップ 1: reverse(DFA):

ステップ 2: subset(reverse(DFA)):

サブセット構築を実行して、DFA 状態のテーブルを構築し、各一意のイプシロン クロージャーからの可能な遷移を表します (^開始状態を$示し、受け入れ状態を示します)。

A = e-closure({s5}) = {s0,s2,s4}
B = e-closure({s0,s1,s2,s3,s4}) = {s0,s1,s2,s3,s4}
C = e-closure({s2,s4}) = {s2,s4}
D = e-closure({s1,s2,s3,s4}) = {s1,s2,s3,s4}

     a   b
-----------
A^$  B   C
B$   B   B
C    D   C
D    D   B

ステップ 3: reverse(subset(reverse(DFA))):

DFA を反転します。一般的なプレフィックスを削除した後、別のパスで一般的なサフィックスを削除できます。

ステップ 4: subset(reverse(subset(reverse(DFA)))):

サブセット構築をもう一度実行して、NFA を最小化します。

A = e-closure({E}) = {A,B}
B = e-closure({B,D}) = {B,D}
C = e-closure({A,B,C,D} = {A,B,C,D}

    a  b
--------
A^$ A  B
B   C  B
C$  C  C

---

参考文献:

• Cooper と Torczon によるコンパイラのエンジニアリング、第 2 版。サブセットの構築については 49 ページで説明されており、Brzozowski のアルゴリズムは 75 ページで説明されています。

• Udacity のコンパイラ: 理論と実践コース、レッスン 3。

上記の図の Graphviz コード:

// initial DFA
digraph G {
    rankdir=LR;
    size="8,5"
    
    node [shape=point]; qi;
    node [shape=doublecircle]; s0 s2 s4;
    node [shape=circle];

    qi -> s0;
    s0 -> s0 [label="a"];
    s0 -> s1 [label="b"];
    s1 -> s2 [label="a"];
    s2 -> s2 [label="a"];
    s2 -> s4 [label="b"];
    s4 -> s4 [label="a,b"];
    s1 -> s3 [label="b"];
    s3 -> s3 [label="b"];
    s3 -> s2 [label="a"];
}

// reverse(DFA)
digraph G {
    rankdir=LR;
    size="8,5"
    
    node [shape=point]; qi;
    node [shape=doublecircle]; s0;
    node [shape=circle];

    qi -> s5;
    s0 -> s0 [label="a"];
    s1 -> s0 [label="b"];
    s2 -> s1 [label="a"];
    s2 -> s2 [label="a"];
    s4 -> s2 [label="b"];
    s4 -> s4 [label="a,b"];
    s3 -> s1 [label="b"];
    s3 -> s3 [label="b"];
    s2 -> s3 [label="a"];
    s5 -> s2 [label="e"];
    s5 -> s0 [label="e"];
    s5 -> s4 [label="e"];
}

// subset(reverse(DFA))
digraph G {
    rankdir=LR;
    size="8,5"
    
    node [shape=point]; qi;
    node [shape=doublecircle]; A B;
    node [shape=circle];

    qi -> A;
    A -> B [label="a"];
    A -> C [label="b"];
    B -> B [label="a,b"];
    D -> B [label="b"];
    C -> D [label="a"];
    C -> C [label="b"];
    D -> D [label="a"];
}

// reverse(subset(reverse(DFA)))
digraph G {
    rankdir=LR;
    size="8,5"
    
    node [shape=point]; qi;
    node [shape=doublecircle]; A;
    node [shape=circle];

    qi -> E;
    B -> A [label="a"];
    C -> A [label="b"];
    B -> B [label="a,b"];
    B -> D [label="b"];
    D -> C [label="a"];
    C -> C [label="b"];
    D -> D [label="a"];
    E -> A [label="e"];
    E -> B [label="e"];
}

// subset(reverse(subset(reverse(DFA))))
digraph G {
    rankdir=LR;
    size="8,5"
    
    node [shape=point]; qi;
    node [shape=doublecircle]; A C;
    node [shape=circle];

    qi -> A;
    A -> A [label="a"];
    A -> B [label="b"];
    B -> B [label="b"];
    B -> C [label="a"];
    C -> C [label="a,b"];
}