乔姆斯基层次结构 - Type-1 上下文相关语言

Question

我试着理解乔姆斯基层次结构的不同层次。

我查了一些例子，这是一个我不太明白的例子。也许有人知道为什么这个不是上下文相关的语言：

S → aA 
A → aA | ε
B → bA

Answer 1

毫无疑问，您提供的语法 G 是上下文无关的（每个规则在左轴有一个非终结符，在右轴有一串终结符和非终结符）。因此，它生成的语言 L 是上下文无关的。因此，由于上下文无关语言的范畴是上下文相关语言的真子集，语言L是上下文敏感的。 （我不知道你在哪里读到语言 L 不是上下文相关的。要么你误读了这个，要么你读到的完全是错误的。）

我来猜测一下造成这种混乱的原因。让我们假设您声称 grammar G（不是 language L）不是上下文敏感的。现在，也许很奇怪，如果一种语言是上下文敏感的，这并不意味着 所有产生这种语言的文法 都是上下文敏感的（其他类别也是如此，除了当然是不受限制的）。如果一种语言是上下文相关的，这意味着 有 上下文相关的语法生成它。因此，即使 L 是上下文相关的，这并不一定意味着 G 也是上下文相关的。

然而，如果 G 是一种上下文无关文法，它不是上下文敏感的，那就很奇怪了。这是否正确取决于您对上下文相关语法的确切定义。如您所见，例如，在 related Wikipedia article 中，上下文相关语法至少有两个替代定义：

1. 一种所有规则都采用 αAβ → αγβ 形式的文法，其中 A 是非终结符，α、β、γ 是终结符和非终结符的字符串。
2. 所有规则都是α→β形式的文法，其中α和β是终结符和非终结符的字符串，但α的长度不大于β的长度。作为例外，起始符号 S 可以有规则 S → ε（否则将被禁止）。

根据定义 1，文法 G 是上下文相关的（上下文字符串 α 和 β 为空）。然而，根据定义 2，语法 G 不是，因为非终结符 A 的空产生式规则不是起始符号。

然而，可以提供等效的语法 G'，它根据两个定义对上下文敏感并生成相同的语言 L。一种这样的语法可以构造如下：

A 生成零个或多个 "a" 的字符串。我们可以将其定义替换为：

A → A' | ε
A' → a | aA'

其中 A' 生成一个或多个 "a" 的字符串。请注意 A 的规则不是递归的。我们可以在 S 和 B 的规则中替换 A 的产生式，然后消除非终结符 A。这给我们：

S → aA' | a
A' → a | aA'
B → bA' | b

根据以上两个定义，此文法（可以通过注意 A' 和 S 产生相同的语言来进一步简化）是上下文相关的。