形式言語の階層

形式言語の階層は形式言語の包含階層であり、言語学や計算機科学、数理論理学などにおいて研究される。計算複雑性理論の記述計算量や複雑性クラスとも密接に関係する。チョムスキー階層が知られているが、1956年に発表されて以来、同じ包含階層上に存在する形式言語が多数見つかっている。また、この包含階層の一部を無限の可算個に分ける階層も幾つか知られている。

包含階層

包含階層とは、その要素である集合がその階層の下方にあるすべての集合の真母集合（つまり「集合１⊃集合２⊃集合３⊃...」）になっている構造である。形式言語はそれぞれ文字列の集合であり、階層の上方にある言語が下方にある言語の文字列をすべて含むのがその包含階層である。これらの形式言語は形式文法やオートマトン、モデル理論等によって定義づけられ、大抵の場合その数学的な研究によって階層の中での位置付けを証明される。

チョムスキー階層

チョムスキー階層は、生成文法と呼ばれる、生成規則による終端および非終端記号からなる文字列の書き換えで定義される形式文法の、バリエーションを軸に定義されている。具体的には、

• 文字列のいかなる書き換えも許される制限なし文法がタイプ-0、
• それぞれの生成規則が非終端記号ひとつのみを書き換える文脈依存文法がタイプ-1、
• 文脈依存文法のうち前後の文字列に依存せず書き換える文脈自由文法がタイプ-2、
• 文脈自由文法のうち書き換えの結果が非終端記号一つまたは終端および非終端記号一つずつである正規文法がタイプ-3で、

これらの文法によって定義される形式言語がそれぞれ帰納的可算言語、文脈依存言語、文脈自由言語、正規言語である。また、それぞれに対応するオートマトンもよく知られている。

個々の言語の解説

タイプ-3内

なお、一番小さな形式言語のクラスは、いかなる集合の部分集合でもある空集合、つまり該当文字列の無い言語とするのが自然である。その上には、文字列を有限のk個羅列して定義できる、有限集合のレイヤーが定義できる。

階層

チョムスキー階層	文法	言語	オートマトン
タイプ-0	制限なし	帰納的可算	チューリングマシン
n/a		帰納	Decider
タイプ-1	文脈依存	文脈依存	線形拘束
n/a	Indexed (en)	Indexed (en)	Nested-stack (en)
n/a	木接合	（弱文脈依存）	Embedded Pushdown (en)
タイプ-2	文脈自由	文脈自由	プッシュダウン
n/a	決定性文脈自由 (en)	決定性文脈自由 (en)	決定性プッシュダウン (en)
タイプ-3	正規	正規	有限
n/a		Star-free (en)	Counter-Free
n/a		Locally threshold-testable
n/a		Locally testable
n/a		Strictly local	Scanners
n/a	--	（文字列の有限集合）	--

参考文献

• Rogers, James and Geoffrey K. Pullum (2007) Aural pattern recognition experiments and the subregular hierarchy. To appear in UCLA Working Papers in Linguistics: Mathematics of Language 10.