Homework SourseProve that the language ak2 epsilon a k epsilon N is not a C
Solution
Algorithm
54 down vote accepted
To my knowledge the pumping lemma is by far the simplest and most-used technique. If you find it hard, try the regular version first, it\'s not that bad. There are some other means for languages that are far from context free. For example undecidable languages are trivially not context free.
That said, I am also interested in other techniques than the pumping lemma if there are any.
EDIT: Here is an example for the pumping lemma: suppose the language L={akkP}
is context free (P is the set of prime numbers). The pumping lemma has a lot of /
quantifiers, so I will make this a bit like a game:
You give a word s
of the language of length at least p
The pumping lemma rewrites it like this: s=uvxyz
with some conditions (|vxy|p and |vy|1
)
You give an integer n0
If uvnxynz
is not in L, you win, L
For this particular language for s
any ak (with kp and k is a prime number) will do the trick. Then the pumping lemma gives you uvxyz with |vy|1. Do disprove the context-freeness, you need to find n such that |uvnxynz|
is not a prime number.
|uvnxynz|=|s|+(n1)|vy|=k+(n1)|vy|
And then n=k+1
will do: k+k|vy|=k(1+|vy|) is not prime so uvnxynzL. The pumping lemma can\'t be applied so L
is not context free.
A second example is the language {www{a,b}}
. We (of course) have to choose a string and show that there\'s no possible way it can be broken into those five parts and have every derived pumped string remain in the language.
The string s=apbpapbp
is a suitable choice for this proof. Now we just have to look at where v and y can be. The key parts are that v or y has to have something in it (perhaps both), and that both v and y (and x) are contained in a length p
substring - so they can\'t be too far apart.
This string has a number of possibilities for where v
and y
might be, but it turns out that several of the cases actually look pretty similar.
or vyb. So then they\'re both contained in one of the sections of continguous as or bs. This is the relatively easy case to argue, as it kind of doesn\'t matter which they\'re in. Assume that |vy|=kp.s, then when we pump, the first half of the new string is ap+kbpk/2, and the second is bk/2apbp. Obviously this is not of the form ww
If they\'re in the first section of a
.
The argument for any of the three other sections runs pretty much the same, it\'s just where the k
and k/2
ends up in the indices.
vxy
straddles two of the sections. In this case pumping down is your friend. Again there\'s several places where this can happen (3 to be exact), but I\'ll just do one illustrative one, and the rest should be easy to figure out from there. straddles the border between the first a section and the first b section. Let vy=ak1bk2 (it doesn\'t matter precisely where the as and bs are in v and y, but we know that they\'re in order). Then when we pump down (i.e. the i=0 case), we get the new string s=apk1bpk2apbp, but then if s could be split into ww, the midpoint must be somewhere in the second a section, so the first half is apk1bpk2a(k1+k2)/2, and the second half is ap(k1+k2)/2bp. Clearly these are not the same string, so we can\'t put v and y
The remaining cases should be fairly transparent from there - they\'re the same ideas, just putting v
and y in the other 3 spots in the first instance, and 2 spots in the second instance. In all cases though, you can pump it in such a way that the ordering is clearly messed up when you split the string in half.
Example 1)
Show that 0i
where i
is a power of 2 is not context free
Assume that vxy
there.
Answer)
If you\'re still confused, here\'s the proof. Let p be the integer of the Pumping Lemma and consider the string 02p. If L was a CFL, then (since 2pp) the PL would apply to 02p we\'d have 02p=uvxyz
with
|vxy|p
|vy|>0
So if we let v=0k,y=0j
, we have from (1), k+j=|vy||vxy|p and from (2), k+j=|vy|>0
. In other words,
0<k+jp
Now pump up: The PL assures us that uv2xy2zL
, and observe
|uv2xy2z|=2p+(k+j)2p+p<2p+2p=2p+1
as long as p>0, so the pumped string uv2xy2z has length strictly between 2p and 2p+1. No such string can be in L, so we have a contradiction to the PL implication that uv2xy2zL and so our initial assumption, that L
was a CFL, must be false.
You could shorten this proof if you knew that (1) any context-free language over a 1-symbol alphabet must be regular and (2) the language L={02nn0}
is not regular.
Example2) How to prove {a^(n^2) | n>0} is not context-free?
Answer)
1 down vote
[Since (a) this is an instance of a standard problem and (b) I wasn\'t able to find it in the archives, I\'ll expand my comment into a hinted solution.]
As usual in problems like this, we assume that the language L
is context free, so the Pumping Lemma applies, meaning that there is an integer p>0 such that we can write the string ap2 as the concatenation of strings uvxyz with |vy|>0 and |vxy|=tp. Hence, we\'ll have
0<|vy|=tp
This means that when we pump uvxyz to uvixyiz we\'ll have
p2<|uvixyiz|=p2+(i1)tp2+(i1)p
Choosing i=2 gives us
p2<|uv2xy2z|p2+p
Now, in length order, the next string in L after ap2 will be a(p+1)2. Here\'s the hint: use this fact to show that uvixyiz can\'t possibly be in L, contradicting the Pumping Lemma consequence that all the pumped strings are in L, so consequently L cannot be a CFL.
| 54 down vote accepted | To my knowledge the pumping lemma is by far the simplest and most-used technique. If you find it hard, try the regular version first, it\'s not that bad. There are some other means for languages that are far from context free. For example undecidable languages are trivially not context free. That said, I am also interested in other techniques than the pumping lemma if there are any. EDIT: Here is an example for the pumping lemma: suppose the language L={akkP} |
