形式言語の階層
出典: フリー百科事典『ウィキペディア（Wikipedia）』
形式言語の階層は形式言語の包含階層であり、言語学や計算機科学、数理論理学などにおいて研究される。計算複雑性理論の記述計算量や複雑性クラスとも密接に関係する。チョムスキー階層が知られているが、1956年に発表されて以来、同じ包含階層上に存在する形式言語が多数見つかっている。また、この包含階層の一部を可算個に分ける階層も幾つか知られている。
目次 |
[編集] 包含階層
包含階層とは、その要素である集合がその階層の下方にあるすべての集合の真母集合（つまり「集合１⊃集合２⊃集合３⊃...」）になっている構造である。形式言語の階層を構成する言語クラスはそれぞれ言語の集合であり、階層の上方にある言語クラスが下方にあるクラスの言語をすべて含むのがその包含階層である。これらの形式言語は形式文法やオートマトン、モデル理論等によって定義づけられ、大抵の場合その数学的な研究によって階層の中での位置付けを証明される。
[編集] チョムスキー階層
チョムスキー階層は、生成規則による終端および非終端記号からなる文字列の書き換えで定義される、生成文法と呼ばれる形式文法のクラスを軸に定義されている。具体的には、
- 文字列のいかなる書き換えも許される制限なし文法がタイプ-0、
- それぞれの生成規則が非終端記号ひとつのみを書き換える文脈依存文法がタイプ-1、
- 文脈依存文法のうち前後の文字列に依存せず書き換える文脈自由文法がタイプ-2、
- 文脈自由文法のうち書き換えが終端記号一つまたは終端および非終端記号一つずつである正規文法がタイプ-3で、
これらの文法によって定義される形式言語がそれぞれ帰納的可算言語、文脈依存言語、文脈自由言語、正規言語である。下方の文法クラスがそれぞれ上方の文法クラスすべての真部分集合となっているため、対応する言語も包含階層が成立する。なお、それぞれに対応するオートマトンもよく知られている。
[編集] 個々の言語クラスの解説
チョムスキー階層の言語クラスごとに解説する。
[編集] タイプ-0内
帰納的可算言語は、部分決定性言語またはチューリング受理性言語とも呼ばれ、対応するオートマトンであるチューリングマシンが受理しない文字列の入力で停止する事が保証されていない言語のクラスである。これを決定性のある、つまりチューリングマシンが常に停止する言語に限定したクラスが帰納言語で、決定性言語またはチューリング決定性言語とも呼ばれる。
これらの計算複雑性はそれぞれ複雑性クラスRとREに対応する。つまり、与えられた文字列が、その言語の文字列である事を確かめるアルゴリズムを書ける言語の集合が帰納的可算言語で、その言語の文字列で無い事も確かめるアルゴリズムが存在する言語の集合が帰納言語である。
[編集] タイプ-1内
文脈依存言語自体は余り使われないが、例えばThe Sound Pattern of Englishなどにみられる生成音韻論の規則（A→B/C_D：「C_D」という環境でAをBに書き換えよ）などは文脈依存文法的である。
文脈依存言語の真部分集合として、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内
[編集] タイプ-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 | -- | （文字列の有限集合） | -- |
[編集] 参考文献
 |
この「形式言語の階層」は、言語学に関連した書きかけの項目です。加筆・訂正等して下さる協力者を求めています（ウィキポータル 言語学）。 |
