グルシコフ法

ウィキペディア

グルシコフ法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/02/02 02:14 UTC 版)

この記事は英語版、ドイツ語版の対応するページを翻訳することにより充実させることができます。（2024年1月） 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。 英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Glushkov's construction algorithm|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。

グルシコフ法（英: Glushkov's construction algorithm）、またはベリー・セティ法（英: Berry-Sethi algorithm）とは、理論計算機科学において正規表現を等価なNFAに変換するアルゴリズムの一つである。

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

アルゴリズムの解説

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

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