乔姆斯基层次结构

乔姆斯基层次结构是一组四个形式语言类，每个类都是上面类别的真子集，并且每个类都对应于一个生成语法和一个识别机器。这个层次结构主要源于诺姆·乔姆斯基和马塞尔-保罗·舒岑伯格在 1950 年代后期关于机制语言学和形式语言的研究。层次结构的各个级别在理论计算机科学和应用计算机科学中都非常有用，因为它们与艾伦·图灵关于算法和可计算性的工作以及编译器设计有关。

这个层次结构的每个级别都包含一类形式语言、一类生成语法（每个语法产生关联类中的语言）和一类机器（每个机器识别关联类中的语言）。在层次结构的每个级别，生成语法的规则变得更加严格，使每类语言成为上面类别的子集。这四个类，从最严格到最不严格，分别是