形式言語の階層

ウィキペディア

形式言語の階層

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/08/15 13:02 UTC 版)

形式言語の階層は形式言語の包含階層であり、言語学や計算機科学、数理論理学などにおいて研究される。計算複雑性理論の記述計算量や複雑性クラスとも密接に関係する。チョムスキー階層が知られているが、1956年に発表されて以来、同じ包含階層上に存在する形式言語が多数見つかっている。また、この包含階層の一部を可算個に分ける階層も幾つか知られている。