Therefore, the language is not context-free.
Example 8.4
Show that the language
is not context-free.
Given m in Theorem 8.1, we pick as our string a m 2
b m . The adversary now
has several choices. The only one that requires much thought is the one shown in
Figure 8.3. Pumping i times will yield a new string with m 2 + (i - 1) k 1 a's and m
+ (i - 1) k 2 b's. If the adversary takes k 1 ≠0, k 2 ≠ 0, we can pick i = 0. Since the
result is not in L. If the opponent picks k 1 =0, k 2 ≠0 or k 1 ≠0, k 2 = 0, then again
with i = 0, the pumped string is not in L. We can conclude from this that L is not
a context-free language.
Figure 8.3
A Pumping Lemma for Linear Languages
We previously made a distinction between linear and nonlinear context-free
Example 8.4
Show that the language
is not context-free.
Given m in Theorem 8.1, we pick as our string a m 2
b m . The adversary now
has several choices. The only one that requires much thought is the one shown in
Figure 8.3. Pumping i times will yield a new string with m 2 + (i - 1) k 1 a's and m
+ (i - 1) k 2 b's. If the adversary takes k 1 ≠0, k 2 ≠ 0, we can pick i = 0. Since the
result is not in L. If the opponent picks k 1 =0, k 2 ≠0 or k 1 ≠0, k 2 = 0, then again
with i = 0, the pumped string is not in L. We can conclude from this that L is not
a context-free language.
Figure 8.3
A Pumping Lemma for Linear Languages
We previously made a distinction between linear and nonlinear context-free