grammar - 为什么这个语法不区分上下文？

Question

我有这个语法：

G = (N, Epsilon, P, S)

和

N = {S, A, B}

Epsilon = {a},

P:    S -> e

      S -> ABA

      AB -> aa

      aA -> aaaA

      A -> a

为什么这是一个只有 0 类型的文法？

我认为是因为aA -> aaaA，但我看不出它与规则有何冲突。

规则必须像这样构建：

x1 A x2 -> x1 B x2 尽管：

A是N的元素；

x1,x2 是 V* 的元素；

B是VV*的元素；

，我在V = N united Epsilon这里看不到问题。

a 来自 V，A 来自 N，而 A 的右边可能有空词，它也是 V* 的一部分，所以左边就可以了。

右边又是x1，是a，那么我们可以说aaA是VV*的一部分，aa是V，A是V*，而右边是x2，所以又是空的。

Answer 1

“规则必须像这样构建：x1 A x2 -> x1 B x2 而：....”是的，这是正确的。但是，存在（类型 1 语法的）规则的等效定义： p->q 其中 p,q 是 V^+ 的元素，并且 length(p)<=length(q) 和 -naturally- p 有一个元素N. 你的语法只有规则，满足这种形式 => 你的语法是 type-1