1

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

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

S → aA 
A → aA | ε
B → bA
4

1 回答 1

0

毫无疑问，您提供的语法G是上下文无关的（每个规则在 LHS 中都有一个非终结符，在 RHS 中具有一串终结符和非终结符）。因此，L它生成的语言是上下文无关的。因此，由于上下文无关语言的范畴是上下文敏感语言范畴的真子集，因此语言L是上下文敏感的。（我不知道您在哪里读到该语言L不区分上下文。要么您误读了此内容，要么您阅读的内容完全是错误的。）

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

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

  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。这给了我们：

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

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

于 2016-03-30T23:17:26.323 回答