乔姆斯基层次结构

在形式语言理论、计算机科学和语言学中，乔姆斯基层次结构，是一种形式语法类的包含层次结构。

这种类型的形式语法由一组有限的生产规则（左手边→右手边）组成，其中每个边由以下符号的有限序列组成。一组有限的非终端符号一组有限的终端符号一个起始符号形式语法为（或产生）形式语言提供了一个公理模式，它是一组（通常是无限的）有限长度的符号序列，可以通过对另一个符号序列（最初只包含起始符号）应用生产规则来构建。一条规则可以通过用出现在其右手边的符号替换其左手边的符号而被应用。一系列的规则应用被称为一个派生。这样的语法定义了形式语言：所有只由终端符号组成的词，可以通过从起始符号开始的派生达到。非终端通常用大写字母表示，终端用小写字母表示，起始符号用S表示。例如，语法中的终端{a,b}，非终端{S,A,B}，生产规则S→ABS→ε（其中ε是空字符串）A→aSB→b和起始符号S，定义了所有形式的词的语言再比如，英语的一个玩具子集的语法是这样的。

句法不正确的句子不能从这个语法中导出。关于更多的自然语言例子和形式语法在该领域的问题，见句子结构语法和句子结构规则。

请注意，对应于递归语言的语法集不是这个层次的成员；这些语法将正确地介于Type-0和Type-1之间。每个常规语言都是无语境的，每个无语境语言都是语境敏感的，每个语境敏感语言都是递归的，每个递归语言都是可递归枚举的。这些都是适当的内涵，也就是说，存在着非语境敏感的可递归列举语言，非语境敏感的语言和非正则的无语境语言。

0型语法包括所有的形式语法。它们确切地产生了所有能被图灵机识别的语言。这些语言也被称为可递归列举的语言或可被图灵识别的语言。请注意，这与递归语言不同，递归语言可以由始终保持的图灵机决定。