|
形式言語の階層形式言語の階層は形式言語の包含階層で、計算理論や形式言語学などにおいて研究される。計算複雑性理論の記述計算量や複雑性クラスとも密接に関係する。1956年に発表されたチョムスキー階層に始まるが、その後の（主に計算理論とその周辺分野での）研究により、一般化・細分化が進められた。また、この包含階層の一部を可算個に分ける階層も幾つか知られている。 包含階層包含階層とは、その要素である集合がその階層の下方にあるすべての集合の真母集合（つまり「集合１⊃集合２⊃集合３⊃...」）になっている構造である。形式言語の階層を構成する言語クラスはそれぞれ言語の集合であり、階層の上方にある言語クラスが下方にあるクラスの言語をすべて含むのがその包含階層である。これらの形式言語は形式文法やオートマトン、モデル理論等によって定義づけられ、大抵の場合その数学的な研究によって階層の中での位置付けを証明される。 チョムスキー階層→詳細は「チョムスキー階層」を参照
チョムスキー階層は、生成規則による終端および非終端記号からなる文字列の書き換えで定義される、生成文法と呼ばれる形式文法のクラスを軸に定義されている。具体的には、
これらの文法によって定義される形式言語がそれぞれ帰納的可算言語、文脈依存言語、文脈自由言語、正規言語である。下方の文法クラスがそれぞれ上方の文法クラスすべての真部分集合となっているため、対応する言語も包含階層が成立する。なお、それぞれに対応するオートマトンもよく知られている。 個々の言語クラスの解説チョムスキー階層の言語クラスごとに解説する。 タイプ-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個羅列して定義できる、有限集合のレイヤーが定義できる。 一覧
参考文献
|
![[icon]](%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:Wiki_letter_w_cropped.svg){kind=small}
