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

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

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

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

工事

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

ステップ1

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

ステップ2a

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

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

、

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

、

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

。

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

ステップ2b

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

ステップ3

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

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

。

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

ステップ4

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

例

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

線形化されたバージョンは
$e'=(a_{1}(a_{2}b_{3})^{*})^{*}+(b_{4}a_{5})^{*}$ 。
文字にインデックスを追加することで、文字が線形化されました。
線形表現の最初の文字、最後の文字、長さ2の因数の集合 $P$ 、 $D$ 、 $Fはそれぞれ$
${\begin{aligned}P(e')&=\{a_{1},b_{4}\}\\D(e')&=\{a_{1},b_{3},a_{5}\}\\F(e')&=\{a_{1}a_{2},a_{1}a_{1},a_{2}b_{3},b_{3}a_{1},b_{3}a_{2},b_{4}a_{5},a_{5}b_{4}\}\end{aligned}}$ 。
空の単語は言語に属しているため、です。 $\Lambda (e')=\{\varepsilon \}$
現地語のオートマトン
$L'=(PB^{*}\cap B^{*}D)\setminus B^{*}(B^{2}\setminus F)B^{*}$
初期状態（1）とアルファベットの5文字それぞれの状態を含む。
$B=\{a_{1},a_{2},b_{3},b_{4},a_{5}\}$ 。
$1 からPの 2 つの状態への遷移、の$ $xから$ $y$ への遷移があり、 $D$ の 3 つの状態が最終的で、これが状態 1 です。文字 $yへのすべての遷移には、文字$ $y$ というラベルが付けられます。 $xy\in F$
インデックスを削除してオートマトンを取得します。 $L(e)$

文字セットの計算

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

$Λ$ については、
$\Lambda (\emptyset )=\emptyset$ 、

$\Lambda (\varepsilon )=\{\varepsilon \}$ 、

$\Lambda (a)=\emptyset$ $各文字a$ について、

$\Lambda (e+f)=\Lambda (e)\cup \Lambda (f)$ 、

$\Lambda (e\cdot f)=\Lambda (e)\cdot \Lambda (f)$ 、そして

$\Lambda (e^{*})=\{\varepsilon \}$ 。
$P$ については、
$P(\emptyset )=P(\varepsilon )=\emptyset$ 、

$P(a)=\{a\}$ $各文字a$ について、

$P(e+f)=P(e)\cup P(f)$ 、

$P(e\cdot f)=P(e)\cup \Lambda (e)P(f)$ 、そして

$P(e^{*})=P(e)$ 。

$D$ についても、積を除いて同じ式が用いられる。

$D(e\cdot f)=D(f)\cup D(e)\Lambda (f)$ 。
長さ2の因数の集合については、
$F(\emptyset )=F(\varepsilon )=F(a)=\emptyset$ $各文字a$ について、

$F(e+f)=F(e)\cup F(f)$ 、

$F(e\cdot f)=F(e)\cup F(f)\cup D(e)P(f)$ 、そして

$F(e^{*})=F(e)\cup D(e)P(e)$ 。

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

プロパティ

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

アプリケーションと決定論的表現

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

参照

アナリティク

注釈と参考文献

^ VM Glushkov (1961). 「オートマトン抽象理論」.ロシア数学概論(ロシア語). 16 (5): 1–53. Bibcode :1961RuMaS..16....1G. doi :10.1070/rm1961v016n05abeh004112. S2CID 250833514.
^ ab ジャン＝エリック・ピン (2016 年 11 月)。オートマトン理論の数学的基礎(PDF)。パリ。{{cite book}}: CS1 maint: location missing publisher (link)
^ ジャック・サカロビッチ (2003 年 2 月)。自動化理論の要素。パリ：ヴイベール。ISBN 978-2711748075。
^ ab Jacques Sakarovitch (2009). Elements of Automata Theory . Cambridge: Cambridge University Press. ISBN 9780521844253。
^ ブリュッゲマン・クライン、アンネ (1993)。「有限オートマトンへの正規表現」。理論的なコンピューターサイエンス。12 (2): 197–213。土井：10.1016/0304-3975(93)90287-4。

外部リンク

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

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

[1] VM Glushkov (1961). 「オートマトン抽象理論」.ロシア数学概論(ロシア語). 16 (5): 1–53. Bibcode :1961RuMaS..16....1G. doi :10.1070/rm1961v016n05abeh004112. S2CID 250833514.

[Pin.2016-2] ジャン＝エリック・ピン (2016 年 11 月)。オートマトン理論の数学的基礎(PDF)。パリ。{{cite book}}: CS1 maint: location missing publisher (link)

[3] ジャック・サカロビッチ (2003 年 2 月)。自動化理論の要素。パリ：ヴイベール。ISBN 978-2711748075。

[Sakarovitch.2009-4] Jacques Sakarovitch (2009). Elements of Automata Theory . Cambridge: Cambridge University Press. ISBN 9780521844253。

[5] ブリュッゲマン・クライン、アンネ (1993)。「有限オートマトンへの正規表現」。理論的なコンピューターサイエンス。12 (2): 197–213。土井：10.1016/0304-3975(93)90287-4。