描述这个上下文无关文法生成的语言

Question

我有以下语法，

该文法中的典型推导是
S => Sb => [aaSb]b => [aa[b]b]b => aabbb 对于 n = 1
S => Sb => [aaSb]b => [aa[aaSb]b]b => [aa[aabb]b]b => aaaabbbb 对于 n = 2

编辑：所以我声称这个语法生成了语言
L = {a^(2n)b^(n+2) : n >= 1}

我很确定我的 a 会 a^(2n) 因为有两个 a在S之前，但是b呢？这里没有 lambda，所以我的 n 来自 n >= 1?.

编辑：
b^(n+1) 和 b^(2n+1) 都是错误的假设，因为如果 n = 3。
我将 b 修改为 b^(n+2)。这样 L 变成 L = {a^(2n)b^(n+2) : n >= 1}

Answer 1

此语法生成的语言是a^(2n) b^(n+m+1)，其中n和m是自然数。为了证明这一点，(a) 我们看到使用语法的产生式派生的任何字符串都与上述匹配，并且 (b) 可以使用语法的产生式派生与上述匹配的任何字符串。

(a) 文法可以而且必须恰好使用规则 (3) 一次。这给出了 b 中的 +1。规则 (2) 的执行可能会发生 n 次，将 2n a 放在前面，将 n b 放在后面，因此2n 和 n 项。规则 (1) 可以执行任意次数 m，因此术语

(b) 给定一个字符串a^(2n) b^(n+m+1)，自然数n和m：使用规则(1)的次数等于m；然后，使用规则（2）的次数等于n；然后，用户规则（3）一次。因此，语法生成字符串。

另一种写出相同答案的方法是 a^2n b^m 和 m > n。

Answer 2

解决这个问题的一种方法是重写语法。请注意，产生式 1 和 2 都以 Sb 结尾，因此我们可以对它们进行左因式分解：

S -> ASb
S -> b
A -> 
A -> aa

从前两个产品中，很容易看出 S 生成 A^n b^{n+1} for n >= 0。

从最后两个作品中，A^n 生成 a^{2k} for 0 <= k <= n。

所以语言是a^{2k} b^{n+1} for n >= 0, 0 <= k <= n。

或者等价地，让m = n - k得到a^{2k} b^{k+m+1} for k,m >= 0。

Describe the language generated by this context-free grammar