grammar - 乔姆斯基语言类型

Question

我试图理解四种不同的乔姆斯基语言类型，但是我发现的定义对我而言实际上没有任何意义。我知道类型0是自由语法，类型1是上下文相关，类型2是上下文无关，而类型3是常规。因此，有人可以解释一下，并将其放在上下文中，谢谢。

Answer 1

语言是属于该语言的一组单词。但是，很多时候，无需列出语言中的每个单词，而是只需指定一组规则即可生成语言单词（仅这些单词）以识别所查询的语言。
注意：可能存在不止一组使用相同语言的规则。
通常，对规则施加的限制越多，语言的表达就越少（可以从规则中生成较少的单词），但是如果单词属于规则指定的语言，则更容易识别。由于存在后者，我们希望确定对规则有最大限制的语言，这些语言仍将允许我们生成相同的语言。
关于规则的几句话：通常，您用四个项目描述正式语言（又称四元组）：

非终结符集（N）
终端符号集（T）
生产规则集（P）
起始符号（S）

终端符号（AKA字母）是语言单词所组成的符号，通常是小写英文字母的子集（例如'a'，'b'，'c'）
非终端符号在单词的生成中标记中间状态，指示可能的变换仍可应用于中间“单词”。终端符号和非终端符号之间没有重叠（即，两组符号的交集为空）。用于非终结符的符号通常是大写英文字母的子集（例如“ A”，“ B”，“ C”）
规则表示对一系列终端符号和非终端符号的可能转换。它们的形式为：左侧->右侧，其中左侧和右侧均由一系列终端符号和非终端符号组成。规则示例：aBc-> cBa，这意味着可以在生成单词的过程中将一系列符号“ aBc”（作为中间“单词”的一部分）替换为系列“ cBa”。
起始符号是专用的非终止符号（通常由S表示），表示单词生成的“根”或“开始”，即，在单词生成系列中应用的第一个规则始终具有起始符号作为其左侧。
当所有非终结词都被替换为终结词时，单词的生成成功结束（因此，最终的“中间词”仅由终结符组成，这表明我们到达了所查询语言的词）。
当并非所有非终结符都已被终结符替换时，单词的生成是不成功的，但是没有可应用于当前中间“单词”的生产规则。在这种情况下，必须按照不同的生产规则应用路径，从起始符号重新开始生成。
例：

L = {T，N，P，S}，

哪里

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表示空字符串（即空符号系列）。
乔姆斯基层次结构中的四种不同类型描述了具有不同表达能力的语法（对规则的不同限制）。

由类型0（或不受限制）的语法生成的语言最具表现力（受限制的程度较小）。递归可枚举的语言集包含可以使用图灵机（基本上是计算机）生成的语言。这意味着，如果您使用的语言比这种类型的语言更具表达力（例如英语），则无法编写一种算法，该算法可以列出该语言的每个（只有这些）单词。规则有一个限制：规则的左侧不能为空（不能将任何符号“突兀地引入”）。

类型1（上下文相关）语法生成的语言是上下文相关语言。规则具有以下形式的限制：alpha A beta-> alpha gamma beta，其中alpha和beta可以为空，且gamma是非空的（例外：S-> epsilon规则，仅当起始符号S不会出现在任何规则的右侧）。这将规则限制为在其左侧至少有一个非终结符，并允许它们具有“上下文”：在此规则示例中，非终结符A可以用γ代替，只有当它被（（在“）alpha和beta的上下文中。规则的应用会保留上下文（即alpha和beta不会更改）。

类型2（无上下文）语法生成的语言是无上下文语言。规则具有以下形式的限制：A-> gamma。这将规则限制为在它们的左侧恰好有一个非终结符，并且没有“上下文”。从本质上讲，这意味着，如果您在中间词中看到非终结符，则可以应用左侧带有该非终结符的任何规则，以将其替换为右侧，而与周围环境无关非终结符的符号。大多数编程语言都有上下文无关的生成语法。

由类型3（常规）语法生成的语言是常规语言。规则具有以下形式的限制：A-> a或A-> aB（如果起始符号S没有出现在任何规则的右侧，则允许规则S-> epsilon），这意味着每个非终端必须精确地产生一个终端符号（也可能会产生一个非终端符号）。正则表达式生成/识别这种类型的语言。


这些限制中的一些可以以保持修改后的语法具有相同表达能力的方式解除/修改。修改后的规则可以允许其他算法识别语言的单词。
请注意（如前所述），一种语言通常可以由多种语法（甚至属于不同类型的语法）生成。语言族的表达能力通常等于可以生成那些语言的限制性最强的语法类型的表达能力（例如，由常规（第3类）语法生成的语言也可以由第2类语法生成，但是它们的表达能力能力仍然是类型3语法的能力）。
例子
常规语法

T = {a，b}
N = {A，B，S}
P = {S-> aA，A-> aA，A-> aB，B-> bB，B-> b}

生成包含单词的语言，这些单词以非零数字“ a”开头，然后以非零数字“ b”开头。请注意，不可能描述一种语言，其中每个单词都由多个“ a”后跟相等数量的“ b”组成，并带有常规语法。
上下文无关的语法

T = {a，b}
N = {A，B，S}
P = {S-> ASB，A-> a，B-> b}

生成包含单词的语言，这些单词以非零个数的“ a”开头，后跟相等数量的“ b”。注意，不可能描述一种语言，其中每个单词都包含多个“ a”，然后是相等数量的“ b”，然后是相等数量的“ c”，并且具有上下文无关的语法。
上下文相关的语法

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}

生成包含以下单词的语言，这些单词以非零个数的“ a”开头，后跟相等数量的“ b”，后跟相等个数“ c”。 H在此语法中的作用是使CB组合“交换”为BC组合，因此B可以在左侧收集，而C可以​​在右侧收集。请注意，无法描述由单词“ a”组成的语言，其中“ a”的数目是上下文相关语法的质数，但是可以编写生成该语言的不受限制的语法。