15

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

4

2 回答 2

25

语言是属于该语言的一组单词。然而，很多时候，与其列出语言中的每个单词，不如指定生成该语言单词的规则集（并且仅是那些规则集）来识别所讨论的语言是什么就足够了。

注意：可以有不止一组描述相同语言的规则。

一般来说，对规则施加的限制越多，语言的表达力就越低（可以从规则中生成的单词越少），但如果单词属于规则指定的语言，则更容易识别。由于后者，我们希望识别对其规则限制最多的语言，这些语言仍然允许我们生成相同的语言。

关于规则的几句话：一般来说，你用四个项目来描述一种正式的语言（又名四元组）：

  1. 非终结符号集( N )
  2. 终端符号集( T )
  3. 生产规则集( P )
  4. 起始符号( 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表示空字符串（即空系列符号）。

乔姆斯基层次结构中的四种不同类型描述了不同表达能力的语法（对规则的不同限制）。

  • 由Type 0（或Unrestricted）语法生成的语言最具表现力（限制较少）。递归可枚举语言集包含可以使用图灵机（基本上是计算机）生成的语言。这意味着如果你有一种比这种类型更具表现力的语言（例如英语），你就不能编写一个算法来列出该语言的每一个（并且只有这些）单词。规则有一个限制：规则的左侧不能为空（不能“突然”引入符号）。

  • 由类型 1（上下文相关）语法生成的语言是上下文相关语言。这些规则的限制是它们的格式为：alpha A beta -> alpha gamma beta，其中alpha和beta 可以为空，而gamma不为空（例外：S-> epsilon规则，仅在以下情况下才允许开始符号 S 不会出现在任何规则的右侧）。这将规则限制为在其左侧至少有一个非终结符并允许它们具有“上下文”：此规则示例中的非终结符 A 可以替换为gamma, 仅当它被 ("is in the context of") alpha和beta包围时。规则的应用保留了上下文（即alpha和beta不变）。

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

  • 由Type 3 ( Regular ) 语法生成的语言是正则语言。规则有以下形式的限制：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's 组成，后跟相同数量的 'b's，后跟相同数量的 'c's 与上下文无关语法。

上下文相关语法

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's 组成，其中 'a's 的数量是具有上下文敏感语法的素数，但可以编写生成该语言的不受限制的语法。

于 2012-05-30T12:21:05.807 回答
1

有4种语法

类型-0：

  • 不受限制的语法接受的语法

  • 递归可枚举语言接受的语言

  • 自动机是图灵机

类型一：

  • 上下文相关语法接受的语法

  • 上下文相关语言接受的语言

  • 自动机是线性有界自动机

2型：

  • 上下文无关语法接受的语法

  • 上下文无关语言接受的语言

  • Automaton 是PushDown 自动机

3型：

  • 正则文法接受的文法

  • 正则语言接受的语言

  • 自动机是有限状态自动机

    • -

Chomsky是一个范式，每个产生式都有形式：

  • A->BC或A->a

乔姆斯基的规则 可以有两个变量或只有一个终端

于 2018-12-26T07:33:48.540 回答