パワーセット構造

計算理論とオートマトン理論において、べき集合構成または部分集合構成は、非決定性有限オートマトン(NFA) を、同じ形式言語を認識する決定性有限オートマトン(DFA) に変換するための標準的な方法です。これは、NFA は柔軟性が追加されているにもかかわらず、一部の DFA が認識できない言語を認識できないことを確立するため、理論的には重要です。また、実際には、構築が容易な NFA をより効率的に実行可能な DFA に変換する上でも重要です。ただし、NFA にn個の状態がある場合、結果として得られる DFA は最大 2 ⁿ個の状態、つまり指数関数的に大きな数になる可能性があり、大規模な NFA ではこの構成が実用的でない場合があります。

この構成は、他のタイプのオートマトンに対する同様の構成と区別するために、ラビン・スコット冪集合構成（または部分集合構成）と呼ばれることもあり、1959年にマイケル・O・ラビンとダナ・スコットによって初めて発表されました^。[1]

直感

与えられた入力文字列に対する DFA の動作をシミュレートするには、常に 1 つの状態、つまり入力のプレフィックスを確認した後でオートマトンが到達する状態を追跡する必要があります。対照的に、NFA をシミュレートするには、一連の状態、つまり、オートマトンが行う非決定的な選択に応じて、入力の同じプレフィックスを確認した後に到達できるすべての状態を追跡する必要があります。入力の特定のプレフィックスの後で状態のセット $S$ に到達できる場合、次の入力シンボル $x$ の後で、到達可能な状態のセットは $S$ と $x$ の決定的な関数です。したがって、到達可能な NFA 状態のセットは、NFA シミュレーションで単一の DFA 状態が DFA シミュレーションで果たすのと同じ役割を果たし、実際、このシミュレーションに現れる NFA 状態のセットは、DFA の状態として再解釈される場合があります。^[2]

工事

べき集合の構築は、入力シンボルを消費せずに状態変換を許可しない NFA (別名:「ε-移動」) に最も直接的に適用されます。このようなオートマトンを5 組 $(Q 、Σ、 T 、 q 0 、 F)$ として定義できます。ここで、 $Q$ は状態のセット、 $Σ$ は入力シンボルのセット、 $T$ は遷移関数 (状態と入力シンボルを状態のセットにマッピングする)、 $q 0$ は初期状態、 $F は$ 受け入れ状態のセットです。対応する DFAには、 $Q$ のサブセットに対応する状態があります。DFA の初期状態は ${q 0}$ (1 要素の) 初期状態のセットです。DFA の遷移関数は、状態 $S ($ $Q$ のサブセットを表す) と入力シンボル $x$ をセット $T (S 、 x) = \cup{T (q 、 x) | q \in S} 、$ $S$ 内の状態から $x$ 遷移によって到達できるすべての状態の集合。DFA の状態 $Sが受理状態となるのは、$ $S$ の少なくとも 1 つの要素がNFA の受理状態である場合に限ります。^[2]^[3]

冪集合構築の最も単純なバージョンでは、DFA のすべての状態の集合は $Q$ の冪集合、つまり $Q$ のすべての可能な部分集合の集合です。しかし、結果として得られる DFA の状態の多くは、初期状態から到達できない可能性があるため役に立たない可能性があります。構築の別のバージョンでは、実際に到達可能な状態のみが作成されます。^[4]

ε移動によるNFA

ε移動を伴うNFA（ε-NFAとも呼ばれる）の場合、ε閉包を計算することでこれらに対処するように構成を変更する必要があります。ε閉包とは、ε移動のみを使用して特定の状態から到達可能なすべての状態の集合です。Van Noordは、この閉包計算をべき集合構成に組み込む3つの可能な方法を認識しています。^[5]

前処理ステップとしてオートマトン全体のε閉包を計算し、ε移動のない同等のNFAを生成し、通常のべき集合構築を適用します。ホップクロフトとウルマン^{[6]も議論したこのバージョンは実装が簡単ですが、}自然言語処理アプリケーションでよく発生する大量のε移動を伴うオートマトンには実用的ではありません。^[5]
べき乗集合の計算中に、アルゴリズムによって考慮される各状態 $q$ のε 閉包を計算します(結果をキャッシュします)。 $\{q'~|~q\to _{\varepsilon }^{*}q'\}$
$べき乗集合の計算中に、アルゴリズムによって考慮される状態の各サブセットQ'$ のε 閉包を計算し、その要素を $Q'$ に追加します。 $\{q'~|~\exists q\in Q',q\to _{\varepsilon }^{*}q'\}$

複数の初期状態

NFAが複数の初期状態を許容するように定義されている場合、^[7]対応するDFAの初期状態はNFAのすべての初期状態の集合、または（NFAにε移動もある場合）ε移動によって初期状態から到達可能なすべての状態の集合である。

例

以下の NFA には 4 つの状態があります。状態 1 は初期状態、状態 3 と 4 は受理状態です。アルファベットは 0 と 1 の 2 つの記号で構成され、ε 移動があります。

この NFA から構築された DFA の初期状態は、状態 1 から ε 移動によって到達可能なすべての NFA 状態の集合、つまり集合 {1,2,3} です。入力シンボル 0 による {1,2,3} からの遷移は、状態 1 から状態 2 への矢印、または状態 3 から状態 4 への矢印のいずれかに従う必要があります。さらに、状態 2 と状態 4 のどちらにも出力 ε 移動はありません。したがって、 $T$ ({1,2,3},0) = {2,4} となり、同じ理由から、NFA から構築された完全な DFA は以下のようになります。

この例からわかるように、DFA の開始状態から到達可能な状態は 5 つあります。NFA 状態セットのべき集合内の残りの 11 セットには到達できません。

複雑

DFA の状態は NFA の状態の集合から構成されるため、 $n$ 状態の NFA は最大で $2 n$ 状態の DFA に変換できます。^{[2]すべての} $n$ に対して、すべての状態の部分集合が最初の部分集合から到達可能な $n$ 状態の NFAが存在するため、変換された DFA はちょうど $2 n$ 状態になり、最悪の場合の時間計算量はΘ( $2 n$ )になります。^[8]^{[9]ほぼこれだけの状態を必要とする簡単な例として、少なくとも} $n$ 文字あり、最後から $n番目が 1 であるアルファベット {0,1} 上の文字列の言語があります。これは$ $($ $n$ $+ 1)$ 状態の NFAで表すことができますが、入力の $n$ 文字の接尾辞ごとに 1 つずつ、合計 $2$ $n 個$ $の DFA 状態が必要になります。n$ $=4$ の図を参照してください。^[4]

アプリケーション

Brzozowski の DFA 最小化アルゴリズムは、べき集合構成を 2 回使用します。入力 DFA を逆言語の NFA に変換し、すべての矢印を反転して初期状態と受け入れ状態の役割を交換し、べき集合構成を使用して NFA を DFA に戻し、このプロセスを繰り返します。他の既知の DFA 最小化アルゴリズムとは異なり、最悪の場合の複雑さは指数関数的ですが、多くの例では、最悪の場合の複雑さが示唆するよりも高速に実行されます。^[10]

$サフラの構成は、 n$ 個の状態を持つ非決定性ビュッヒオートマトンを決定性ミュラーオートマトン、または2 ^O(^$n$^log^$n$^{)個の状態を持つ決定性}ラビンオートマトンに変換するもので、その機構の一部としてべき集合構成を使用している。^[11]

参考文献

^ Rabin, MO ; Scott, D. (1959). 「有限オートマトンとその決定問題」IBM Journal of Research and Development . 3 (2): 114–125. doi :10.1147/rd.32.0114. ISSN 0018-8646.
^ abc Sipser, Michael (1997). 「定理 1.19」.計算理論入門. pp. 55–56. ISBN 0-534-94728-X。
^ ホップクロフト、ジョン E. ;ウルマン、ジェフリー D. (1979)。「DFA と NFA の同値性」。オートマトン理論、言語、計算入門。マサチューセッツ州リーディング: アディソン・ウェスレー。pp. 22–23。ISBN 0-201-02988-X。
^ abc Schneider, Klaus (2004). リアクティブシステムの検証: 形式手法とアルゴリズム. Springer. pp. 210–212. ISBN 978-3-540-00296-3。
^ ab Van Noord, Gertjan (2000). 「サブセット構築におけるイプシロン移動の扱い」.計算言語学. 26 (1): 61–76. arXiv : cmp-lg/9804003 . doi :10.1162/089120100561638. S2CID 5622079.
^ ホップクロフト＆ウルマン（1979）、26-27頁。
^ Rothe, Jörg (2006). 複雑性理論と暗号学: 暗号複雑性入門. 理論計算機科学テキスト. Springer. pp. 21–22. ISBN 9783540285205。。
^ Lupanov, Oleg B. (1963). 「2種類の有限ソースの比較」. Problemy Kibernetiki . 9 : 321–326.
^ Moore, Frank R. (1971). 「決定論的、非決定論的、双方向有限オートマトン間の等価性の証明における状態セットサイズの境界について」IEEE Transactions on Computers . C-20 (10): 1211–1214. doi :10.1109/TC.1971.223108. S2CID 206618275.。
^ Brzozowski, JA (1963). 「確定イベントの正規正規表現と最小状態グラフ」。Proc. Sympos. Math. Theory of Automata (ニューヨーク、1962)。 Polytechnic Press of Polytechnic Inst. of Brooklyn、ブルックリン、ニューヨーク、pp. 529–561。MR 0175719。
^ Safra, S. (1988). 「ω-オートマトンにおける複雑さについて」。第29回コンピュータサイエンスの基礎に関する年次シンポジウム(FOCS '88)の議事録。ワシントン DC、米国: IEEE コンピュータ協会。pp. 319–327。doi : 10.1109 /SFCS.1988.21948。。

さらに読む

アンダーソン、ジェームズ・アンドリュー（2006年）。オートマトン理論と現代的応用。ケンブリッジ大学出版局。pp.43-49。ISBN 978-0-521-84887-9。

[1] Rabin, MO ; Scott, D. (1959). 「有限オートマトンとその決定問題」IBM Journal of Research and Development . 3 (2): 114–125. doi :10.1147/rd.32.0114. ISSN 0018-8646.

[sipser-2] Sipser, Michael (1997). 「定理 1.19」.計算理論入門. pp. 55–56. ISBN 0-534-94728-X。

[hu-3] ホップクロフト、ジョン E. ;ウルマン、ジェフリー D. (1979)。「DFA と NFA の同値性」。オートマトン理論、言語、計算入門。マサチューセッツ州リーディング: アディソン・ウェスレー。pp. 22–23。ISBN 0-201-02988-X。

[schneider-4] Schneider, Klaus (2004). リアクティブシステムの検証: 形式手法とアルゴリズム. Springer. pp. 210–212. ISBN 978-3-540-00296-3。

[vannoord-5] Van Noord, Gertjan (2000). 「サブセット構築におけるイプシロン移動の扱い」.計算言語学. 26 (1): 61–76. arXiv : cmp-lg/9804003 . doi :10.1162/089120100561638. S2CID 5622079.

[6] ホップクロフト＆ウルマン（1979）、26-27頁。

[7] Rothe, Jörg (2006). 複雑性理論と暗号学: 暗号複雑性入門. 理論計算機科学テキスト. Springer. pp. 21–22. ISBN 9783540285205。。

[8] Lupanov, Oleg B. (1963). 「2種類の有限ソースの比較」. Problemy Kibernetiki . 9 : 321–326.

[moore71-9] Moore, Frank R. (1971). 「決定論的、非決定論的、双方向有限オートマトン間の等価性の証明における状態セットサイズの境界について」IEEE Transactions on Computers . C-20 (10): 1211–1214. doi :10.1109/TC.1971.223108. S2CID 206618275.。

[10] Brzozowski, JA (1963). 「確定イベントの正規正規表現と最小状態グラフ」。Proc. Sympos. Math. Theory of Automata (ニューヨーク、1962)。 Polytechnic Press of Polytechnic Inst. of Brooklyn、ブルックリン、ニューヨーク、pp. 529–561。MR 0175719。

[11] Safra, S. (1988). 「ω-オートマトンにおける複雑さについて」。第29回コンピュータサイエンスの基礎に関する年次シンポジウム(FOCS '88)の議事録。ワシントン DC、米国: IEEE コンピュータ協会。pp. 319–327。doi : 10.1109 /SFCS.1988.21948。。