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

ナビゲーションに移動 検索に移動
m
有限モデル理論・記述計算量
m ((リンク))
m (有限モデル理論・記述計算量)
'''形式言語の階層'''は[[形式言語]]の包含[[階層構造|階層]]であり、[[言語学]]や[[計算機科学]]、[[数理論理学]]などにおいて研究される。[[計算複雑性理論]]の[[記述計算量]]や[[複雑性クラス]]とも密接に関係する。[[チョムスキー階層]]が知られているが、[[1956年]]に発表されて以来、同じ包含階層上に存在する[[形式言語]]が多数見つかっている。また、この包含階層の一部を[[可算無限集合|無限の可算個]]に分ける階層も幾つか知られている。
 
== 包含階層 ==
包含階層とは、その要素である集合がその階層の下方にあるすべての集合の真母集合(つまり「集合1⊃集合2⊃集合3⊃...」)になっている構造である。形式言語はそれぞれ文字列の集合であり、階層の上方にある言語が下方にある言語の文字列をすべて含むのがその包含階層である。これらの形式言語は[[形式文法]]や[[オートマトン]]、[[有限モデル理論|モデル理論]]等によって定義づけられ、大抵の場合その数学的な研究によって階層の中での位置付けを証明される。
 
== チョムスキー階層 ==
309

回編集

案内メニュー