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

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

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

其中

e == epsilon

和

是不必要的，但是为了清晰起见添加了

Answer 3

是的，这听起来确实像家庭作业，但有一个提示：

每次匹配“a”时，都必须匹配“c”。与匹配“b”相同。

Answer 4

S->aSc|A A->bAc|λ

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

Answer 5

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

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

Answer 6

我的回答：

S -> aAc |

A -> BC | bAc

其中 S 是起始符号。

Answer 7

L = {epsilon, ac, bc, abcc, abbccc, aabbcccc,.....}

每次增加a或b时，我们可以尝试增加c。

S -> aSc|bSc|epsilon

Answer 8

如果 L= a^n b^n c^n+m 表示 L={e,ac,bc,aacc,bbcc,----,abcc,aabbcccc,abbccc,aaabbcccccc,-------} 其中 e 是 epsilon

S-> aSc/e/A

A-> 理学士/电子

喜欢现在生成aabbbccccc， aSc 将生成 aacc（平衡 a 和 c）那么A将取代S并生成aabbbccccc（平衡b和c）

Answer 9

S-> aBc/epsilon B-> bBc/S/epsilon 这也照顾了字母顺序