语言是属于该语言的单词的集合。然而，很多时候，不必列出该语言中的每个单词，而是指定生成该语言的单词（并且仅生成这些单词）的一组规则来识别所讨论的语言是什么就足够了。
Note：可以有不止一组描述同一种语言的规则。
一般来说，对规则的限制越多，语言的表达能力越差（从规则中可以生成的单词越少），但更容易识别单词是否属于规则指定的语言。由于后者，我们希望识别对其规则限制最多的语言，这些语言仍然允许我们生成相同的语言。
关于规则的几句话：一般来说，您用四个项目（又称四元组）来描述正式语言：
- 的集合非终结符 (N)
- 的集合终端符号 (T)
- 的集合生产规则 (P)
- The 开始符号 (S)
终止符号（又称字母）是语言单词组成的符号，通常是小写英文字母的子集（例如“a”、“b”、“c”）
非终结符标记单词生成中的中间状态，指示可能的变换仍然可以应用于中间“单词”。终结符号和非终结符号之间没有重叠（即两个集合的交集为空）。用于非终结符的符号通常是大写英文字母的子集（例如“A”、“B”、“C”）
这些规则表示一系列终结符和非终结符的可能变换。它们的形式为：左侧 -> 右侧，其中左侧和右侧均由一系列终结符和非终结符组成。示例规则：aBc -> cBa，这意味着一系列符号“aBc”（作为中间“单词”的一部分）可以在单词生成期间被系列“cBa”替换。
起始符号是专用的非终结符号（通常用 S 表示），表示单词生成的“根”或“开始”，即在单词生成系列中应用的第一个规则始终具有起始符号作为其左侧。
当所有非终结符都被终结符替换时，单词的生成就成功完成了（因此最终的“中间单词”仅由终结符组成，这表明我们到达了所讨论语言的单词）。
当并非所有非终结符都已被终结符替换，但没有可应用于当前中间“词”的产生规则时，词的生成不成功。在这种情况下，生成必须从起始符号重新开始，遵循产生式规则应用的不同路径。
Example:
L={T, N, P, S},
where
T={a,b,c}
N={A,B,C,S}
P={S->A, S->AB, S->BC, A->a, B->bb, C->ccc}
它表示三个单词的语言：“a”、“abb”和“bbccc”
规则应用示例：
S->AB->aB->abb
其中我们 1) 从起始符号 (S) 开始，2) 应用第二条规则（用 AB 替换 S），3) 应用第四条规则（用 a 替换 A），4) 应用第五条规则（用 bb 替换 B） ）。由于生成的“abb”中没有非终结符，因此它是该语言的一个单词。
当一般谈论规则时，希腊符号alpha, beta, gamma等表示（可能为空的）一系列终结符+非终结符；希腊字母epsilon表示空字符串（即空的符号系列）。
中的四种不同类型乔姆斯基层次结构描述不同表达能力的语法（规则的不同限制）。
-
生成的语言Type 0 (or 无限制) 语法最具表现力（限制较少）。的集合递归可枚举languages 包含可以使用图灵机（基本上是计算机）生成的语言。这意味着，如果您有一种比这种类型更具表现力的语言（例如英语），您就无法编写一个可以列出该语言的每个（且仅这些）单词的算法。这些规则有一个限制：规则的左侧不能为空（不能“突然”引入任何符号）。
-
生成的语言Type 1 (上下文相关) 语法是上下文相关语言。这些规则有以下形式的限制：alpha A beta -> 阿尔法伽玛贝塔, where alpha and 贝塔可以是空的，并且gamma非空（例外：S->epsilon规则，仅当起始符号 S 未出现在任何规则的右侧时才允许）。这限制了规则在其左侧至少有一个非终结符，并允许它们有一个“上下文”：此规则示例中的非终结符 A 可以替换为gamma，仅当它被包围时（“在...的上下文中”）alpha and beta。规则的应用保留了上下文（即alpha and beta不会改变）。
-
生成的语言Type 2 (上下文无关) 语法是上下文无关语言。这些规则有以下形式的限制：A ->gamma。这限制了规则在其左侧只有一个非终结符并且没有“上下文”。这本质上意味着，如果您在中间词中看到非终结符，则可以应用左侧具有该非终结符的任何规则来将其替换为右侧，无论周围环境如何非终结符的。大多数编程语言都有上下文无关的生成语法。
-
生成的语言Type 3 (Regular) 语法是Regular语言。这些规则有以下形式的限制：A->a 或 A->aB（规则 S->epsilon如果起始符号 S 没有出现在任何规则的右侧，则允许该符号），这意味着每个非终结符必须恰好产生一个终结符（也可能产生一个非终结符）。这常用表达生成/识别这种类型的语言。
其中一些限制可以解除/修改，以保持修改后的语法具有相同的表达能力。修改后的规则可以允许其他算法识别某种语言的单词。
请注意（如前所述）一种语言通常可以由多种语法（甚至属于不同类型的语法）生成。语言族的表达能力通常等同于可以生成这些语言的最严格的语法类型的表达能力（例如，由常规（类型 3）语法生成的语言也可以由类型 2 语法生成，但是它们的表达能力能力仍然是类型 3 语法的能力）。
Examples
The 常规语法
T={a, b}
N={A,B,S}
P={S->aA, A->aA, A->aB, B->bB, B->b}
生成包含以非零数量的“a”开头，后跟非零数量的“b”的单词的语言。请注意，用常规语法来描述一种语言是不可能的，其中每个单词都由多个“a”和后跟相同数量的“b”组成。
The 上下文无关语法
T={a, b}
N={A,B,S}
P={S->ASB, A->a, B->b}
生成包含以非零数量的“a”开头，后跟相同数量的“b”的单词的语言。请注意，不可能用上下文无关语法来描述每个单词由多个“a”、后跟相同数量的“b”、后跟相同数量的“c”组成的语言。
The 上下文相关语法
T={a,b,c}
N={A,B,C,H,S}
P={S->aBC, S->aSBC, CB->HB, HB->HC, HC->BC, aB->ab, bB->bb, bC->bc, cC->cc}
生成 tha 语言，其中包含以非零数量的 'a' 开头的单词，后跟相同数量的 'b'，最后是相同数量的 'c'。 H在此语法中的作用是能够将CB组合“交换”为BC组合，因此B可以聚集在左侧，而C可以聚集在右侧。请注意，不可能用上下文相关语法来描述单词由一系列“a”组成的语言，其中“a”的数量是素数，但可以编写生成该语言的无限制语法。
