出典: フリー百科事典『ウィキペディア(Wikipedia)』
グルシコフ法(英: Glushkov's construction algorithm)、またはベリー・セティ法(英: Berry-Sethi algorithm)とは、理論計算機科学において正規表現を等価なNFAに変換するアルゴリズムの一つである。
名称は1961年にこのアルゴリズムを提唱したヴィクトル・グルシコフが由来である。
対象の正規表現をまず構文木として書き出す。この構文木の節は正規表現の諸規則に従い(正規表現同士の結合、推移閉包、和集合はまた正規表現)、葉は入力文字セットの要素、つまり文字列を構成する文字を表す。以下の変換ステップはこの構文木に基づいて行われる。
構文木の根から下にある節や葉へと動く点を仮定すると、対象の正規表現が表す文字列が逐次的に生成される。この仮定された点に基づいて、有限オートマトンを構築する。このアルゴリズムの時間計算量はである。
- 構文木のすべての節において、節に属する述語 を求める。このステップは後行順のDFSで実現可能である。
- 構文木のすべての節において、節に属する集合 を求める。このステップは後行順のDFSで実現可能である。
- 構文木のすべての節において、節に属する集合 を求める。このステップは先行順のDFSで実現可能である。
- 構文木のすべての節において、節に属する集合 を求める。このステップは後行順のDFSで実現可能である。
- 最後に次のようにまとめる:
- 構築するオートマトンの状態の集合は
- オートマトンの初期状態は
- オートマトンの終了状態は
- , if and
- , if
- オートマトンの状態遷移関数は
- , if and is marked with , and
- , if and is marked with .
記号 は構文木を動き回る点を表す。結果として生成されたオートマトンは多くの場合非決定的であるが、部分集合構成法により決定性をもたせることができる。
- 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.