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 的数字？我猜这一定是一个上下文无关的语法，如果是这样，它应该是怎样的？

score 8 · Accepted Answer

似乎应该是这样的：

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

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

score 4 · Accepted Answer

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

哪里e == epsilon和X是不必要的，但为了清楚起见添加

score 2 · Accepted Answer

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

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

score 0 · Accepted Answer

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

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

score 0 · Accepted Answer

好吧，伙计们，我将这样做：

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

score 0 · Accepted Answer

0

我的答案：

S -> aAc | aSc

A -> 公元前 | bAc

其中 S 是起始符号。

于 2019-12-07T15:52:45.853 回答

6 回答 6