文脈依存言語とは? わかりやすく解説

Weblio 辞書 > 同じ種類の言葉 > 言葉 > 言葉 > 言語 > 文脈依存言語の意味・解説 

文脈依存言語

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/01/03 10:17 UTC 版)

文脈依存言語(ぶんみゃくいそんげんご、Context-sensitive Language)は、文脈依存文法で定義される形式言語である。これはチョムスキー階層の四つの文法のひとつであるが、理論的にも実用的にも最も使われることが少ない文法でもある。

計算属性

計算性という観点では、文脈依存言語は線形拘束オートマトン(線形拘束された非決定性チューリングマシン)と等価である。これは、テープ長が kn セルに制限された非決定性チューリングマシンである。ここで n は入力の長さ、k はそのマシンに対応した定数である(つまりテープ長は入力の長さに比例する)。要するに、そのようなマシンで判定できる形式言語は文脈依存言語であり、文脈依存言語はそのようなマシンで判定できる。

このクラスの言語の集合は非決定性チューリングマシンの線形空間に受容されるのでNLIN-SPACENon-deterministic Linear Space)として知られている。同様に決定性チューリングマシンに受容される言語については LIN-SPACE と呼ぶ。LIN-SPACENLIN-SPACE の部分集合であることは明らかである。LIN-SPACE = NLIN-SPACE であるかどうかは不明であるが、一般に等価ではないと考えられている。

文脈自由ではない文脈依存言語の例として、L = { an : n素数 } がある。これを示す簡単な方法は線形拘束オートマトンを使うことである。

他に、L = { anbncn : n は正の整数 } 等がある。

文脈依存言語の属性

  • ふたつの文脈依存言語に対して和集合、積集合、連結を施した結果も文脈依存言語である。
  • 文脈依存言語の補集合は文脈依存言語である。
  • 文脈自由言語は文脈依存言語に含まれる(ただしその文脈依存文法の定義に S → ε という規則が含まれる場合のみ)。

関連項目





文脈依存言語と同じ種類の言葉


英和和英テキスト翻訳>> 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