乔姆斯基层级

形式语法是计算理论中描述语言生成规则的形式化系统，最经典的分类是乔姆斯基层级：正则语法、上下文无关语法、上下文相关语法和无限制语法，四者依次对应有限状态自动机、下推自动机、线性有界自动机和图灵机所能识别的语言类。