グルシュコフの構築アルゴリズム

コンピュータサイエンス理論、特に形式言語理論において、ヴィクトル・ミハイロヴィチ・グルシコフによって発明されたグルシコフの構築アルゴリズムは、与えられた正規表現をそれと同等の非決定性有限オートマトン(NFA) に変換します。したがって、このアルゴリズムは、正規表現と非決定性有限オートマトン (同じクラスの形式言語の 2 つの抽象表現) の間の橋渡しとなります。

正規表現は、テキスト処理ユーティリティの「検索と置換」のような操作で、高度な検索パターンを便利に記述するために使用できます。Glushkov のアルゴリズムを使用して、これを NFA に変換できます。NFA の状態数は正規表現のシンボル数に 1 を加えた数に等しいため、NFA は本質的に小さくなります。その後、NFA をべき乗集合構造によって決定論的にし、最小化して、指定された正規表現に対応する最適なオートマトンを取得できます。後者の形式は、コンピューターでの実行に最適です。

別の、より理論的な観点から見ると、グルシュコフのアルゴリズムは、NFA と正規表現の両方がまったく同じ言語、つまり正規言語を受け入れるという証明の一部です。グルシュコフのアルゴリズムの逆は、有限オートマトンを正規表現に変換するクリーネのアルゴリズムです。グルシュコフの構築によって得られるオートマトンとトンプソンの構築アルゴリズムによって得られるオートマトンとは、ε 遷移が削除されると、 同じになります。

正規表現eが与えられると、グルシュコフ構築アルゴリズムはeが受け入れる言語を受け入れる非決定性オートマトンを作成する。^{[1] [2] : 59–61}構築には4つのステップがある。 ${\displaystyle L(e)}$

式の線形化。式eに現れるアルファベットの各文字の名前が変更され、各文字が新しい式 に最大で 1 回出現するようになります。グルシュコフの構成は、基本的に がローカル言語を表すという事実に依存しています。Aを古いアルファベット、B を新しいアルファベットとします。 ${\displaystyle e'}$${\displaystyle e'}$ ${\displaystyle L(e')}$

集合、、の計算。最初の、 は の単語の最初の文字として現れる文字の集合です。2 番目の、 は の単語の終わりになる文字の集合です。最後の 、は の単語に現れる文字のペアの集合、つまり の単語の長さ 2 の因数の集合です。これらの集合は数学的に次のように定義されます。 ${\displaystyle P(e')}$${\displaystyle D(e')}$${\displaystyle F(e')}$${\displaystyle P(e')}$${\displaystyle L(e')}$${\displaystyle D(e')}$${\displaystyle L(e')}$${\displaystyle F(e')}$${\displaystyle L(e')}$${\displaystyle L(e')}$

${\displaystyle P(e')=\{x\in B\mid xB^{*}\cap L(e')\neq \emptyset \}}$、

${\displaystyle D(e')=\{y\in B\mid B^{*}y\cap L(e')\neq \emptyset \}}$、

${\displaystyle F(e')=\{u\in B^{2}\mid B^{*}uB^{*}\cap L(e')\neq \emptyset \}}$。

これらは、以下で説明するように、式の構造に対する帰納法によって計算されます。

この単語が に属する場合は空単語を含む 集合 の計算 、そうでない場合は空集合 の計算。正式には、これは であり 、 は空単語を表します。 ${\displaystyle \Lambda (e')}$${\displaystyle L(e')}$${\displaystyle \Lambda (e')=\{\varepsilon \}\cap L(e')}$${\displaystyle \epsilon }$

、、、およびで定義される ローカル 言語を認識するオートマトンを計算します。定義により、集合P、D、およびFで定義されるローカル言語は、文字Pで始まり、文字Dで終わり、長さ 2 の因子がFに属し、オプションで空単語も含まれる単語の集合です。つまり、次の言語です。 ${\displaystyle P(e')}$${\displaystyle D(e')}$${\displaystyle F(e')}$${\displaystyle \Lambda (e')}$

${\displaystyle L'=(PB^{*}\cap B^{*}D)\setminus B^{*}(B^{2}\setminus F)B^{*}\cup \Lambda (e')}$。

厳密に言えば、この線形化された表現によって表されるローカル言語のオートマトンを計算することがグルシュコフの構築です。

線形化を削除し、各インデックス文字B を元の文字Aに置き換えます。

^{[2] : 60–61の}正規表現 を考えてみましょう。 ${\displaystyle e=(a(ab)^{*})^{*}+(ba)^{*}}$

P、D、F、およびΛの集合の計算は、正規表現 に対して帰納的に行われます。 ∅ 、ε（空の言語と空の単語を含むシングルトン言語の記号）、文字、および演算の結果の値を指定する必要があります。 ${\displaystyle e'}$${\displaystyle +,\cdot ,^{*}}$

最もコストのかかる演算は、 Fの計算のための集合の積です。

得られたオートマトンには非決定性があり、正規表現の文字数に1を加えた数の状態を持つ。さらに、ε遷移を除いた場合、 グルシュコフのオートマトンとトンプソンのオートマトンは同じであることが示された^{[3] :215  [4]。}

式によるオートマトン計算は頻繁に行われ、検索機能、特にUnixの grepコマンドで体系的に使用されています。同様に、XMLの仕様でもこのような構造が使用されています。より効率的にするために、決定論的表現と呼ばれるある種の正規表現が研究されてきました。^{[4] [5]}

• アナリティク

• グルシュコフ、フォロー、アンチミロフオートマトンを統一的に構築する

• アルゴリズムと計算：第14回国際シンポジウム、ISAAC