我正在学习有限自动机和语法测试,我被这个问题困扰了:
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 的数字?我猜这一定是上下文无关语法,如果是这样,应该怎么样?
看起来应该是这样的:
A->aAc | aBc | ac | epsilon
B->bBc | bc | epsilon
在构建过程中需要强制计算C'c。为了表明它是上下文无关的,我会考虑使用Pump Lemma。
S -> X
X -> aXc | Y
Y -> bYc | e
其中
e == epsilon
和 X
是不必要的,但是
为了清晰起见添加了
是的,这听起来确实像家庭作业,但有一个提示:
每次匹配“a”时,都必须匹配“c”。与匹配“b”相同。
S->aSc|A A->bAc|λ
这意味着当你得到 a 时,你至少有 1 c,或者如果你得到 a 和 b,你必须有 2 c。 我希望它有帮助
好吧,伙计们,这就是我要做的:
P={S::=X|epsilon,
X::=aXc|M|epsilon,
M::=bMc|epsilon}
我的回答:
S -> aAc |
A -> BC | bAc
其中 S 是起始符号。
L = {epsilon, ac, bc, abcc, abbccc, aabbcccc,.....}
每次增加a或b时,我们可以尝试增加c。
S -> aSc|bSc|epsilon
如果 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)
S-> aBc/epsilon B-> bBc/S/epsilon 这也照顾了字母顺序