用泵引理证明语言是上下文无关的
Proving language is context-free with pumping lemma
我即将进行一项测试，使用泵引理来证明一种语言是否是上下文无关的。我正在尝试解决一些练习题，但进展并不顺利...
练习题为：
对于 a) 到 j)，证明以下语言是否是上下文无关的。如果是上下文无关的，给出生成它的上下文无关文法。
前两个是：
a) {a^(2i+1) b^(3k+2) c^(4k+3) d^(5i+4) | i >= 0, k >= 0}
b) {a^i b^i c^k d^i | i >= 1, k >= 1}
如果有人能解决前两个问题，并详细说明他们是如何解决的，我相信我将能够自己解决其余的问题（c 到 j）。
a 是上下文无关的：
A -> aBdddd
B -> aaBddddd
B -> C
C -> bbbCcccc
C -> D
D -> bbccc
B 不是上下文无关的。让我们假设它是。因此我们有一个整数 p 泵引理成立。让我们看一下b中的以下单词：
a^p b^p c d^p
根据泵引理，这个词可以表示为序列uvwxy，使得|vwx| < p, 而u v^i w x^i y也在B.
让我们看看vx：
情况 1：vx 包含 "c"。如果是这样的话，那uwy应该也在B里面，但是B要求我们至少有一个"c"。所以那种情况是不可能的。
情况 2：vx 不包含 "c"。它最多必须包含 "a"、"b" 或 "c" 中的两个（否则 |vwx| 将大于 p）。所以uv^2wx^2y不会包含相等数量的a、b、c，也不在B中。
因此，B 不是上下文无关语言。
我即将进行一项测试，使用泵引理来证明一种语言是否是上下文无关的。我正在尝试解决一些练习题，但进展并不顺利...
练习题为： 对于 a) 到 j)，证明以下语言是否是上下文无关的。如果是上下文无关的，给出生成它的上下文无关文法。
前两个是：
a) {a^(2i+1) b^(3k+2) c^(4k+3) d^(5i+4) | i >= 0, k >= 0}
b) {a^i b^i c^k d^i | i >= 1, k >= 1}
如果有人能解决前两个问题，并详细说明他们是如何解决的，我相信我将能够自己解决其余的问题（c 到 j）。
a 是上下文无关的：
A -> aBdddd
B -> aaBddddd
B -> C
C -> bbbCcccc
C -> D
D -> bbccc
B 不是上下文无关的。让我们假设它是。因此我们有一个整数 p 泵引理成立。让我们看一下b中的以下单词： a^p b^p c d^p
根据泵引理，这个词可以表示为序列uvwxy，使得|vwx| < p, 而u v^i w x^i y也在B.
让我们看看vx：
情况 1：vx 包含 "c"。如果是这样的话，那uwy应该也在B里面，但是B要求我们至少有一个"c"。所以那种情况是不可能的。
情况 2：vx 不包含 "c"。它最多必须包含 "a"、"b" 或 "c" 中的两个（否则 |vwx| 将大于 p）。所以uv^2wx^2y不会包含相等数量的a、b、c，也不在B中。
因此，B 不是上下文无关语言。