この記事は 英語版、ドイツ語版の対応するページを翻訳することにより充実させることができます。（2024年1月）翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
- 英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。
- 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。
- 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。
- 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。
- 翻訳後、
{{翻訳告知|en|Glushkov's construction algorithm|…}}をノートに追加することもできます。
- Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。
|
グルシコフ法（英: Glushkov's construction algorithm）、またはベリー・セティ法（英: Berry-Sethi algorithm）とは、理論計算機科学において正規表現を等価なNFAに変換するアルゴリズムの一つである。
名称は1961年にこのアルゴリズムを提唱したヴィクトル・グルシコフが由来である。
アルゴリズムの解説
編集
対象の正規表現をまず構文木として書き出す。この構文木の節は正規表現の諸規則に従い（正規表現同士の結合、推移閉包、和集合はまた正規表現）、葉は入力文字セットの要素、つまり文字列を構成する文字を表す。以下の変換ステップはこの構文木に基づいて行われる。
構文木の根から下にある節や葉へと動く点を仮定すると、対象の正規表現が表す文字列が逐次的に生成される。この仮定された点に基づいて、有限オートマトンを構築する。このアルゴリズムの時間計算量は
である。
変換ステップ
編集
- 構文木のすべての節
において、節に属する述語 ![{\displaystyle empty[r]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a30c9aab98f2ac4558933a66cc91dc879b8ccb10)
を求める。このステップは後行順のDFSで実現可能である。
- 構文木のすべての節 において、節に属する集合
![{\displaystyle first[r]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/866b1d244cb70856ae23e2c509f6c9ba94196adf)
を求める。このステップは後行順のDFSで実現可能である。
- 構文木のすべての節 において、節に属する集合
![{\displaystyle next[r]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c512e1840fdd22373e7b87dd70441b790bc8e3d6)
を求める。このステップは先行順のDFSで実現可能である。
- 構文木のすべての節 において、節に属する集合
![{\displaystyle last[r]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/885c5cc88e499c36909670959a2435fbd0e810a2)
を求める。このステップは後行順のDFSで実現可能である。
- 最後に次のようにまとめる:
- 構築するオートマトンの状態の集合は
- オートマトンの初期状態は
- オートマトンの終了状態は
![{\displaystyle last[e]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/30cdf38e7841f695d5008172ae44fdf96ef218e1)
, if ![{\displaystyle empty[e]=false}](https://wikimedia.org/api/rest_v1/media/math/render/svg/46a125fe7f030b077c11d2234209ef782720bee0)
and![{\displaystyle \{\bullet e\}\cup last[e]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6f43d163c7c42e028278cbc010b5adec1f835f60)
, if ![{\displaystyle empty[e]=true}](https://wikimedia.org/api/rest_v1/media/math/render/svg/741567b9a763eedfc96e0b48768efe07d920f8a7)
- オートマトンの状態遷移関数は
, if ![{\displaystyle i\in first[e]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ce1d5478377d7d353671e79412584978ded1f63)
and 
is marked with 
, and
, if ![{\displaystyle i'\in next[i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b21c26758e6e39fe346b76ae8cb88109f53fe7ce)
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.
