我只是想知道我的CFG对于第一种语言是否正确。
以下语言是字母表｛a，b，c｝
第一语言
｛xcy|x和y是具有相同数量a的字符串｝
我的CFG
S->AaASAA|c|AcA
A->AA|b|c|epsilon
第二语言
｛a^ib^jc^k|i>=j+k｝
在我的课上，我们证明了同一种语言没有CFG，如果i=j=k，这有什么不同？这甚至有CFG吗？如果是这样的话，我想不出任何一种cfg能产生这种语言，我能想到的唯一一种就是满足a的数量大于或等于b的数量加上c的数量，其中顺序无关紧要。
第一种语言的CFG是正确的，尽管我更喜欢像这样毫不含糊地写A：
A -> epsilon | Ab | Ac
第二语言：
S -> M | aS
M -> N | aMc
N -> epsilon | aNb
注意：是的，这是一个家庭作业问题，但我不认为在这里提供答案会破坏这种特殊的学习体验。一旦你看到它，你就会明白，如果你没有明白，你可以用头撞它很长一段时间，却一无所获。