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

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 和 X 是不必要的，但是
为了清楚起见添加了

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-> 丙烯酰胺| aSc

A-> 公元前 | bAc

其中 S 是起始符号。

Answer 7

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

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

S-> aSc|bSc|epsilon

Answer 8

if **L= a^n b^n c^n+m**

表示

L={e,ac,bc,aacc,bbcc,----,abcc,aabbcccc,abbccc,aaabbccccc,-------}

其中 'e' 是 epsilon

S-> aSc/e/A
A-> bSc/e

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

Answer 9

S-> aBC/ε
B-> bBC/S/ε
这也考虑了字母的顺序