チョムスキー標準形とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > チョムスキー標準形の意味・解説 

チョムスキー標準形

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/06/21 15:19 UTC 版)

形式言語理論において、次のような生成規則のみからなる文法をチョムスキー標準形(チョムスキーひょうじゅんけい)という。

または
または

ここで、 および 非終端記号終端記号であり、 は開始記号を表し、 は空列を表すものとする。

また、チョムスキー標準形は次のような性質を持つ。

  • チョムスキー標準形で表すことのできる文法は全て文脈自由であり、また全ての文脈自由文法は、これと等価なチョムスキー標準形の文法に書き換えることができる。
  • 型の規則(空列を導出する文法に含まれる)を除いて、チョムスキー標準形の文法における全ての生成規則は拡張的である。つまり、終端記号と非終端記号からなる文字列に生成規則を適用して生成される文字列の長さは元の文字列の長さよりも等しいか、あるいは長くなる。
  • 長さ の文字列を導出するには、 回以上規則を適用する必要がある。
  • 1つの非終端記号から導出される非終端記号は常に2つとなり、構文木二分木で表されるため、木の深さは最大でも文字列の長さである。

これらの性質から、言語理論や計算複雑性理論の分野における証明では、しばしばチョムスキー標準形が用いられる。また、CYKアルゴリズム(チョムスキー標準形の文法が与えられた文字列を生成できるか否かを決定するアルゴリズム)のように、様々な効率的なアルゴリズムの基礎となっている。

チョムスキー標準形の名前はノーム・チョムスキーにちなむ。

関連項目




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「チョムスキー標準形」の関連用語

チョムスキー標準形のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



チョムスキー標準形のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのチョムスキー標準形 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS