Chomsky Hierarchy

乔姆斯基体系（chomsky hierarchy） 是把形式语法按表达能力分类的体系，包含四个层次：

文法	别称	语言	自动机	产生式规则
0 型文法	无限制文法、短语结构文法	递归可枚举语言	图灵机	$α \to β$
1 型文法	上下文有关语法	上下文有关语言	线性有界非确定图灵机	$α A β \to α γ β$
2 型文法	上下文无关语法	上下文无关语言	非确定下推自动机	$A \to γ$
3 型文法	正规文法	正则语言	有限状态自动机	$A \to a B$ $A \to a$

四个层次包含关系如图，正则语言一定是上下文无关语言，而上下文语言不一定是正则语言。

Wikipedia

The Chomsky hierarchy is a containment hierarchy of classes of formal grammars. A formal grammar describes how to form strings from a language's vocabulary (or alphabet) that are valid according to the language's syntax. Linguist Noam Chomsky theorized that four different classes of formal grammars existed that could generate increasingly complex languages. Each class can also completely generate the language of all inferior classes.

Each class can also completely generate the language of all inferior classes.^[1]

https://en.wikipedia.org/wiki/Chomsky_hierarchy ↩︎