CFG对于A = B和C = D（长度）
我知道如何为具有相同计数的 a 和 b 或具有相同计数的 c 和 的字符串构建上下文无关语法d：
S → ε S → ε
S → SASBS S → SCSDS
S → SBSAS S → SDSCS
A → a C → c
B → b D → d
但是，我不知道如何为 a 和 b 的计数相同的字符串创建语法，并且c 和 d 的计数为 相同。对于诸如 cadbdabc 之类的字符串，我的尝试会失败，其中配对彼此之间（例如：c、、d、）。因此，如果有人可以提供帮助，我将不胜感激。
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您试图识别的语言不是不含上下文的，因此您将无法为其构建无上下文的语法。
要看一下，请记住，语言 a n c m b n n d m 不是无上下文。 （您可以轻松地证明使用泵送引理；实际上，这是经典的例子之一。请以 m 和 n 均大于泵送常数< m p ; u 和 x 带有空字符串 - 泵送0重复 - 必须成为一个平等性的一个。）
现在，令 l 是您的语言，并考虑 l a*c*c*b*d*的交叉点。无上下文语言和普通语言的交集是保证是上下文free < /a>， a*c*b*d*显然是规律的。因此，如果 l 是无上下文的，那么 l a*c*c*b*d*将是上下文-自由的。但是 l ∩a*c*b*d*恰恰是语言 a n c c m b n d m ，这不是上下文；矛盾。因此， l 不能无上下文。
The language you are trying to recognise is not context-free, so you're not going to be able to construct a context-free grammar for it.
To see that, remember that the language ancmbndm is not context-free. (You can easily prove that using the pumping lemma; in fact, it's one of the classic examples. Take a string where both m and n are greater than the pumping constant p; any substring uvx whose length is no greater than p can contain at most two different symbols with two different repetition counts; so replacing u and x with the empty string -- pumping 0 repetitions -- must make one of the equalities false.)
Now, let L be your language, and consider the intersection L ∩ a*c*b*d*. The intersection of a context-free language and a regular language is guaranteed to be context-free, and a*c*b*d* is obviously regular. So if L were context-free, then L ∩ a*c*b*d* would be context-free. But L ∩ a*c*b*d* is precisely the language ancmbndm, which is not context-free; a contradiction. Thus, L cannot be context-free.