ホーム
おまかせ表示
付近
ログイン
設定
寄付
ウィキペディアについて
免責事項
検索
「形式言語の階層」の版間の差分
言語
ウォッチリストに追加
編集
履歴の双方向閲覧
← 古い編集
新しい編集 →
削除された内容
追加された内容
ビジュアル
ウィキテキスト
2008年5月4日 (日) 23:45時点における版
編集
ペー
(
会話
|
投稿記録
)
311
回編集
包含階層の定義、チョムスキー階層の位置付け
← 古い編集
2008年5月4日 (日) 23:58時点における版
編集
取り消し
ペー
(
会話
|
投稿記録
)
311
回編集
定義
新しい編集 →
1行目:
'''形式言語の階層'''は
[[形式言語]]の包含[[階層構造|階層]]であり、言語学や計算機科学、数理論理学などにおいて研究される。[[計算複雑性理論]]の[[複雑性クラス]]とも密接に関係する。
[[チョムスキー階層]]が知られているが、[[1956年]]に発表されて以来、同じ
[[階層構造|
包含階層
]]
上に存在する[[形式言語
]]の[[集合
]]が多数見つかっている。また、この包含階層の一部を[[可算無限集合|無限の可算個]]に分ける階層も幾つか知られている。
== 包含階層 ==