「形式言語の階層」の版間の差分

→‎タイプ-1内: タイプ-1内
(→‎タイプ-1内: タイプ-1内)
文脈依存言語の真部分集合として、Alfred Ahoによって発見された'''Indexed Languages''' (IL) が知られている。ILは、文脈自由文法の非終端記号に[[スタック]]として機能する'index'を添記したIndexed Grammar によって定義される。対応するオートマトンはNested stack automatonである。
 
文脈自由言語により近い所には、[[自然言語]]の研究から'''[[弱文脈依存言語]]'''というクラスが設定されている。弱文脈依存言語は、そのクラスの言語の持つべきおおまかな特徴によって定義されている点で、形式言語のクラスとしては異色である。自然言語に対する重要性からこのクラスに属するが文脈自由でない文法が言語学などで多く提案されており、代表的なものに[[木接合文法]]がある。
 
弱文脈依存言語に相当するより明確な形式言語の階層に'''Control Language Hierarchy'''がある。Control Language Hierarchyは可算個の包含階層で、Level-1クラスを文脈自由言語とし、Level-''k'' (k>1) クラスは(少なくともkの小さいうちは)弱文脈依存言語の定義を満たす。このうちLevel-2クラスは[[木接合文法]]、Combinatory Categorial Grammar、Head Grammar、Linear Indexed Grammarの四つの形式文法が定義するクラスと同一である。
 
=== タイプ-2内 ===
309

回編集