如何构造生成此语言的语法？

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 。

Answer 2

是的，这听起来像家庭作业，但提示：

每次匹配'a'时，您必须匹配'c'。相同的匹配'b'。

Answer 3

S -> X
X -> aXc | Y
Y -> bYc | e

其中 e == epsilon 和 X 是不必要的 为清晰起见而添加

Answer 4

S-＆GT; ASC | A A-＆GT; BAC |＆＃955;

这意味着当你得到一个至少你有1 c或如果你得到a和b你必须有2 c。 我希望它有所帮助

Answer 5

好吧，伙计们，我就是这样做的：

P={S::=X|epsilon,
   X::=aXc|M|epsilon,
   M::=bMc|epsilon}