grammar - 我如何构建生成这种语言的语法？

Question

我正在学习有限自动机和语法测试，但我被这个问题困扰:

Construct a grammar that generates L:
L = {a^n b^m c^m+n|n>=0, m>=0}

我相信我的作品应该遵循这样的思路:

    S->aA | aB
    B->bB | bC
    C->cC | c Here's where I have doubts

我的 C 产生式如何记住 m 和 n 的数字？我猜这一定是一个上下文无关的语法，如果是这样，它应该怎么样？

Answer 1

看起来应该是这样的:

A->aAc | aBc | ac | epsilon
B->bBc | bc | epsilon

您需要在构建过程中强制计算 C'c。为了显示它是上下文无关的，我会考虑使用 Pump Lemma .