トンプソンの建設

コンピュータサイエンスにおいて、トンプソンの構築 アルゴリズムはマクノートン・ヤマダ・トンプソンアルゴリズムとも呼ばれ、^[1]正規表現を同等の非決定性有限オートマトン(NFA) に変換する手法です。^{[2]この NFA は}文字列を正規表現と照合するために使用できます。このアルゴリズムはケン・トンプソンが考案しました。

正規表現と非決定性有限オートマトンとは、形式言語の 2 つの表現です。たとえば、テキスト処理ユーティリティは、高度な検索パターンを記述するために正規表現を使用しますが、NFA はコンピューターでの実行に適しています。したがって、このアルゴリズムは、正規表現を NFA にコンパイルできるため、実用上興味深いものです。理論的な観点から見ると、このアルゴリズムは、両方がまったく同じ言語、つまり正規言語を受け入れるという証明の一部です。

NFA は、べき乗集合の構築によって決定論的に作成され、その後最小化されて、指定された正規表現に対応する最適なオートマトンが得られます。ただし、NFA は直接解釈することもできます。

与えられた 2 つの正規表現が同じ言語を記述しているかどうかを判断するには、それぞれを、トンプソンの構成、べき乗集合の構成、およびDFA 最小化によって、同等の最小決定性有限オートマトンに変換します。結果のオートマトンが状態の名前変更まで一致する場合のみ、正規表現の言語は一致します。

このアルゴリズムは、式を構成する部分式に分割することで再帰的に動作し、そこから一連のルールを使用してNFAが構築されます。 ^[3]より正確には、正規表現Eから、遷移関数Δ ^{[説明が必要]}を持つ得られたオートマトンAは、次の特性に従います。

• A には、他のどの状態からもアクセスできない初期状態q ₀が 1 つだけあります。つまり、任意の状態qと任意の文字aに対して、q _{0 は}含まれません。${\displaystyle \Delta (q,a)}$
• A には、他のどの状態からも相互にアクセスできない最終状態q _{f が}1 つだけあります。つまり、任意の文字aについて、.${\displaystyle \Delta (q_{f},a)=\emptyset }$
• c を正規表現Eの連結数とし、s を括弧以外の記号の数（つまり、|、*、a、ε ）とします。このとき、 Aの状態数は2 s − c （ Eのサイズに比例）です。
• 任意の状態から出る遷移の数は最大 2 です。
• m個の状態と各状態から最大e 個の遷移を持つ NFA は長さnの文字列をO ( emn )の時間でマッチングできるため、トンプソン NFA は固定サイズのアルファベットを仮定すると線形時間でパターンマッチングを行うことができます。^{[4] [より良い情報源が必要]}

^{以下の規則はAho et al. (2007)、 [1]} p. 122に従って描かれている。以下では、N ( s )とN ( t )はそれぞれ部分式sとtのNFAである。

空表現εは次のように変換される。

入力アルファベットの記号aは次のように変換さ れます。

結合式 s | tは次のように変換されます。

状態q はε を経由してN ( s ) またはN ( t )の初期状態に移行します。それらの最終状態は NFA 全体の中間状態となり、2 つの ε 遷移を経由して NFA の最終状態に統合されます。

連結式 stは次のように変換される。

N ( s )の初期状態はNFA全体の初期状態です。N ( s )の最終状態はN ( t )の初期状態になります。N ( t )の最終状態はNFA全体の最終状態です。

クリーネスター式 s ^*は次のように変換される。

ε遷移は、NFA の初期状態と最終状態を、その間のサブ NFA N ( s ) を介して接続します。N ( s ) の内部最終状態から内部初期状態への別の ε遷移により、スター演算子に従って 式sを繰り返すことができます。

• 括弧内の式( s )はN ( s )そのものに変換されます。

これらの規則では、空表現とシンボル規則を基本ケースとして使用して、任意の正規表現を同等のNFAに変換できることを構造的帰納法で証明することができます。 ^[1]

ここで、結果を伴う小さな非公式の例と、アルゴリズムの段階的な適用を伴うより大きな例の 2 つの例を示します。

下の図は、 上の Thompson の構築結果を示しています(ε|a*b)。紫色の楕円はa、青緑色の楕円はa*、緑色の楕円はb、オレンジ色の楕円はa*b、青色の楕円はεに対応します。

(0|(1(01*(00)*0)*1)*)*例として、図は、3 の倍数である 2 進数の集合を表す 正規表現に対する Thompson の構築アルゴリズムの結果を示しています。

{ ε, "0", "00", "11", "000", "011", "110", "0000", "0011", "0110", "1001", "1100", "1111" , "00000", ... }。

右上の部分は式の論理構造 (構文ツリー) を示しており、「.」は連結 (可変個数であると想定) を表します。部分式は参照用にa - qと名付けられています。左側の部分は、トンプソンのアルゴリズムから生成された非決定性有限オートマトンを示しており、各部分式のエントリ状態と終了状態はそれぞれマゼンタとシアンで色付けされています。わかりやすくするために、遷移ラベルの ε は省略されています。ラベルのない遷移は実際には ε 遷移です。ルート式qに対応するエントリ状態と終了状態は、それぞれオートマトンの開始状態と受け入れ状態です。

アルゴリズムの手順は次のとおりです。

同等の最小決定性オートマトンを以下に示します。

トンプソンのアルゴリズムは、正規表現からNFAを構築するためのいくつかのアルゴリズムの1つです。 ^[5]以前のアルゴリズムは、マクノートンとヤマダによって提案されました。^[6]トンプソンの構築とは逆に、クリーネのアルゴリズムは有限オートマトンを正規表現に変換します。

ε 遷移が削除されると、 Glushkov の構築アルゴリズムはThompson の構築に類似します。

ウィキメディア・コモンズには、トンプソンの構成 (形式言語理論)に関連するメディアがあります。