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

タイプ-0と-1加筆
(→‎タイプ-3内: 一番下。)
(タイプ-0と-1加筆)
'''形式言語の階層'''は[[形式言語]]の包含[[階層構造|階層]]であり、[[言語学]]や[[計算機科学]]、[[数理論理学]]などにおいて研究される。[[計算複雑性理論]]の[[記述計算量]]や[[複雑性クラス]]とも密接に関係する。[[チョムスキー階層]]が知られているが、[[1956年]]に発表されて以来、同じ包含階層上に存在する[[形式言語]]が多数見つかっている。また、この包含階層の一部を[[可算無限集合|無限の可算個]]に分ける階層も幾つか知られている。
 
== 包含階層 ==
包含階層とは、その要素である集合がその階層の下方にあるすべての集合の真母集合(つまり「集合1⊃集合2⊃集合3⊃...」)になっている構造である。形式言語の階層を構成する言語クラスはそれぞれ文字列言語の集合であり、階層の上方にある言語クラスが下方にあるクラスの言語の文字列をすべて含むのがその包含階層である。これらの形式言語は[[形式文法]]や[[オートマトン]]、[[有限モデル理論|モデル理論]]等によって定義づけられ、大抵の場合その数学的な研究によって階層の中での位置付けを証明される。
る。
 
== チョムスキー階層 ==
チョムスキー階層は、生成文法と呼ばれる、生成規則による終端および非終端記号からなる文字列の書き換えで定義される形式文法の、バリエーションクラスを軸に定義されている。具体的には、
* 文字列のいかなる書き換えも許される[[制限なし文法]]がタイプ-0、
* それぞれの生成規則が非終端記号ひとつのみを書き換える[[文脈依存文法]]がタイプ-1、
* 文脈依存文法のうち前後の文字列に依存せず書き換える[[文脈自由文法]]がタイプ-2、
* 文脈自由文法のうち書き換えの結果終端記号一つまたは終端および非終端記号一つずつである[[正規文法]]がタイプ-3で、
これらの文法によって定義される形式言語がそれぞれ[[帰納的可算言語]]、[[文脈依存言語]]、[[文脈自由言語]]、[[正規言語]]である。下方の文法クラスがそれぞれ上方の文法クラスすべての真部分集合となっているめ、対応する言語も包含階層が成立する。なお、それぞれに対応する[[オートマトン]]もよく知られている。
 
== 個々の言語クラスの解説 ==
チョムスキー階層の言語クラスごとに解説する。
 
=== タイプ-0内 ===
'''帰納的可算言語'''は、部分決定性言語またはチューリング受理性言語とも呼ばれ、対応するオートマトンである[[チューリングマシン]]が受理しない文字列の入力で停止する事が保証されていない言語のクラスである。これを決定性のある、つまりチューリングマシンが常に停止する言語に限定したクラスが'''[[帰納言語]]'''で、決定性言語またはチューリング決定性言語とも呼ばれる。
 
これらの計算複雑性はそれぞれ複雑性クラス[[R (計算複雑性理論)|R]]と[[RE (計算複雑性理論)|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である。
 
 
 
=== タイプ-2内 ===
なお、一番小さな形式言語のクラスは、いかなる集合の部分集合でもある[[空集合]]、つまり該当文字列の無い言語とするのが自然である。その上には、文字列を有限のk個羅列して定義できる、有限集合のレイヤーが定義できる。
 
== 階層一覧 ==
{| class="wikitable"
!チョムスキー階層
|-
| n/a
| [[木接合文法|木接合]] など
| ([[弱文脈依存言語|弱文脈依存]])
| Embedded Pushdown ([[w:Embedded pushdown automaton|en]])
309

回編集