グルシコフ法のソースを表示

{{Expand language
|langcode = en
|otherarticle = Glushkov's construction algorithm
|langcode2 = de
|otherarticle2 = Berry-Sethi-Verfahren
|date= 2024年1月
}}

'''グルシコフ法'''（{{lang-en-short|Glushkov's construction algorithm}}）、または'''ベリー・セティ法'''（{{lang-en-short|Berry-Sethi algorithm}}）とは、[[理論計算機科学]]において[[正規表現]]を等価な[[非決定性有限オートマトン|NFA]]に変換する[[アルゴリズム]]の一つである。 

名称は[[1961年]]にこのアルゴリズムを提唱した[[ヴィクトル・グルシコフ]]が由来である。

== アルゴリズムの解説 ==
対象の正規表現をまず[[木構造|構文木]]として書き出す。この構文木の節は正規表現の諸規則に従い（正規表現同士の[[文字列結合|結合]]、[[推移閉包]]、[[和集合]]はまた正規表現）、葉は入力文字セットの要素、つまり文字列を構成する文字を表す。以下の変換ステップはこの構文木に基づいて行われる。

構文木の根から下にある節や葉へと動く点を仮定すると、対象の正規表現が表す文字列が逐次的に生成される。この仮定された点に基づいて、[[有限オートマトン]]を構築する。このアルゴリズムの[[ランダウの記号#一般的なオーダー|時間計算量]]は<math>\mathcal O (n^2)</math>である。

=== 変換ステップ ===
# 構文木のすべての節<math>r</math>において、節に属する述語 <math>empty[r]</math>を求める。このステップは後行順の[[深さ優先探索|DFS]]で実現可能である。
# 構文木のすべての節<math>r</math>において、節に属する集合 <math>first[r]</math>を求める。このステップは後行順のDFSで実現可能である。
# 構文木のすべての節<math>r</math>において、節に属する集合 <math>next[r]</math>を求める。このステップは先行順のDFSで実現可能である。
# 構文木のすべての節<math>r</math>において、節に属する集合 <math>last[r]</math>を求める。このステップは後行順のDFSで実現可能である。
# 最後に次のようにまとめる:
## 構築するオートマトンの状態の集合は<math>\{ \bullet e \} \cup \{i \bullet \mid \mbox{i is leaf}\}</math>
## オートマトンの初期状態は <math> \bullet e </math>
## オートマトンの終了状態は
###<math>last[e]</math>, if <math>empty[e] = false</math> and
###<math>\{\bullet e\} \cup last[e]</math>, if <math>empty[e] = true</math>
## オートマトンの状態遷移関数は
###<math>( \bullet e, a, i\bullet)</math>, if <math>i \in first[e]</math> and <math>i</math> is marked with <math>a</math>, and
###<math>( i \bullet, a, i'\bullet)</math>, if <math>i' \in next[i]</math> and <math>i'</math> is marked with <math>a</math>.

記号 <math>\bullet</math> は構文木を動き回る点を表す。結果として生成されたオートマトンは多くの場合非決定的であるが、[[部分集合構成法]]により決定性をもたせることができる。

== 参考文献 ==
* Gérard Berry, Ravi Sethi: ''From regular expressions to deterministic automata.'' In: ''Theoretical Computer Science.'' 48, 1986, {{ISSN|0304-3975}}, S. 117–126.
* Viktor M. Glushkov: ''The abstract theory of automata.'' In: ''Russian Mathematical Surveys.'' 16, 1961, {{ISSN|0036-0279}}, S. 1–53.
{{デフォルトソート:くるしこふほう}}
[[Category:形式言語]]
[[Category:コンパイラ構築]]
[[Category:有限オートマトン]]
[[Category:アルゴリズム]]