形式言語の階層
From Wikipedia, the free encyclopedia
チョムスキー階層
チョムスキー階層は、生成規則による終端および非終端記号からなる文字列の書き換えで定義される、生成文法と呼ばれる形式文法のクラスを軸に定義されている。具体的には、
- 文字列のいかなる書き換えも許される制限なし文法がタイプ-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内
文脈自由文法は、自然言語や、プログラミング言語を含む人工言語において、その多く(決して全てではない)を説明することができる。これは人間の認知構造の特性を表している可能性がある。
一方で、自然言語の中には文脈自由文法で記述できない例も存在し、特にスイスドイツ語における格の一致を伴う交差依存関係は、自然言語が必ずしも文脈自由文法で記述できないことを強く示唆している。[1]
コンピューターにおける計算の観点からは、文脈自由言語はプッシュダウンオートマトンで処理できるため、現在主流のメモリ管理手法であるスタックとヒープによる実装が容易である。そのため、マークアップ言語によるウェブページ(HTMLなど)や数式(TeXなど)の記述を含め、現在のコンピュータ言語は文脈自由言語であることが少なくない。
タイプ-3内
なお、一番小さな形式言語のクラスは、いかなる集合の部分集合でもある空集合、つまり該当文字列の無い言語とするのが自然である。その上には、文字列を有限のk個羅列して定義できる、有限集合のレイヤーが定義できる。
