工学で用いられる生成文法
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/10/25 17:00 UTC 版)
「生成文法」の記事における「工学で用いられる生成文法」の解説
多層的アプローチで変換規則を用いる文法は少なく見積もってチョムスキー階層においてタイプ-2文法(文脈自由文法)より強力である。現実のコンピュータに対応するのは制限されたチューリングマシンである線状有界オートマトンであり、これが扱いうるのはタイプ-1文法(文脈依存文法)までである。実際に現在のコンピュータに変換規則を実装しようとすると、可能な組み合わせが指数関数的に増加し、組み合わせ的爆発(計算論的爆発)を起こす場合がある。そこで、1980年代前後より、コンピュータへの実装という観点でより現実的な、タイプ-2文法よりやや強力であるところに押さえた単層的アプローチとしての非変換論的生成文法が提案されている。中でも一般化句構造文法(GPSG)とその発展である主辞駆動句構造文法(HPSG)、TAG(Tree-Adjoining Grammar)などがコンピュータ科学においては変換論的生成文法よりも集中的に研究されている。
※この「工学で用いられる生成文法」の解説は、「生成文法」の解説の一部です。
「工学で用いられる生成文法」を含む「生成文法」の記事については、「生成文法」の概要を参照ください。
- 工学で用いられる生成文法のページへのリンク