グルシコフ法

グルシコフ法（テンプレート:Lang-en-short）、またはベリー・セティ法（テンプレート:Lang-en-short）とは、理論計算機科学において正規表現を等価なNFAに変換するアルゴリズムの一つである。

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

アルゴリズムの解説

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

構文木の根から下にある節や葉へと動く点を仮定すると、対象の正規表現が表す文字列が逐次的に生成される。この仮定された点に基づいて、有限オートマトンを構築する。このアルゴリズムの時間計算量は$𝒪(n^2)$である。

変換ステップ

1. 構文木のすべての節$r$において、節に属する述語 $empty[r]$を求める。このステップは後行順のDFSで実現可能である。
2. 構文木のすべての節$r$において、節に属する集合 $first[r]$を求める。このステップは後行順のDFSで実現可能である。
3. 構文木のすべての節$r$において、節に属する集合 $next[r]$を求める。このステップは先行順のDFSで実現可能である。
4. 構文木のすべての節$r$において、節に属する集合 $last[r]$を求める。このステップは後行順のDFSで実現可能である。
5. 最後に次のようにまとめる:
   1. 構築するオートマトンの状態の集合は$\{\bullet e\}\cup \{i\bullet \mid \text{i is leaf}\}$
   2. オートマトンの初期状態は $\bullet e$
   3. オートマトンの終了状態は
      1. $last[e]$, if $empty[e]=false$ and
      2. $\{\bullet e\}\cup last[e]$, if $empty[e]=true$
   4. オートマトンの状態遷移関数は
      1. $(\bullet e,a,i\bullet )$, if $i\in first[e]$ and $i$ is marked with $a$, and
      2. $(i\bullet ,a,i^{\prime }\bullet )$, if $i^{\prime }\in next[i]$ and $i^{\prime }$ is marked with $a$.

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

参考文献

• Gérard Berry, Ravi Sethi: From regular expressions to deterministic automata. In: Theoretical Computer Science. 48, 1986, テンプレート:ISSN, S. 117–126.
• Viktor M. Glushkov: The abstract theory of automata. In: Russian Mathematical Surveys. 16, 1961, テンプレート:ISSN, S. 1–53.