如何构造满足0≤n≤m的语言L={a^m b^n c^(m+n)}的上下文无关文法？

你的思路方向是对的，但问题出在原文法允许生成b^n c^n而不需要对应的a——也就是当S直接推导到B时，会得到m=0但n>0的字符串，这违反了n≤m的约束；另外，原文法还允许生成a^m b^n c^(m+n)中n>m的情况（比如m=1,n=2的abbccc），因为B可以生成任意数量的b和c，没有和a的数量绑定。

要解决这个问题，我们需要保证每生成一个b，必须同时生成一个对应的a，这样b的数量永远不会超过a的数量。同时，我们还要保留只生成a和c的情况（对应n=0）。

正确的上下文无关文法如下：

S → ε
S → a S c
S → a b S c c

文法解释 #

1. S → ε：生成空字符串，对应m=0,n=0的情况，符合约束。
2. S → a S c：在已有的合法字符串前后分别添加a和c，相当于m增加1，n不变，保证m≥n仍然成立（原m≥n，新m+1≥n）。这条规则用来生成n=0的所有字符串，比如a^m c^m。
3. S → a b S c c：在已有的合法字符串前后分别添加ab和cc，相当于m和n各增加1，原m≥n则新m+1≥n+1，仍然满足约束。这条规则用来生成n≥1的所有合法字符串，比如a^m b^n c^(m+n)（n≤m）。

验证例子 #

• 生成a²b c³：S → a S c → a a b S c c c → a a b ε c c c = aabccc，对应m=2,n=1，1≤2，符合条件。
• 生成a²b²c⁴：S → a b S c c → a b a b S c c c c → a b a b ε c c c c = aabbcccc，对应m=2,n=2，2≤2，符合条件。
• 无法生成abbccc（m=1,n=2）：要生成2个b，必须使用两次S → a b S c c，这会同时生成2个a，最终得到的是a²b²c⁴，而不是abbccc，完美避免了n>m的情况。

内容的提问来源于stack exchange，提问作者Sehnsucht