Prove that the following language is not context free:
L = {a^3^n : n >= 0}
To prove that the given language L = {a^3^n : n ≥ 0} is not context-free, we can use the pumping lemma for context-free languages. The pumping lemma provides a way to show that a language is not context-free by assuming that it is context-free and then deriving a contradiction.
The pumping lemma states that if L is a context-free language, then there exists a pumping length p such that any string s in L with |s| ≥ p can be divided into five parts: s = uvwxy, satisfying the following conditions:
1. |vwx| ≤ p
2. |vx| ≥ 1
3. For all k ≥ 0, the string u(v^k)w(x^k)y is also in L
Now, let's use the pumping lemma to prove that L = {a^3^n : n ≥ 0} is not context-free.
Assume that L is a context-free language and let p be the pumping length. We will consider a string s = a^3^p in L.
Since s = a^3^p, its length |s| = 3^p ≥ p. According to the pumping lemma, we can divide s into five parts: s = uvwxy, satisfying the conditions mentioned above.
Let's analyze the possible locations of v and x within s:
1. Both v and x contain only "a"s: In this case, pumping the string s by increasing the value of k will result in a string that contains more than one block of "a^3" due to the condition that |vx| ≥ 1. However, this new string will not be in L since the number of "a"s must always be a power of 3.
2. Both v and x contain "a"s and "e" (empty string): In this case, if we pump the string s by increasing the value of k, the resulting string will contain fewer "a"s than the original string s, and therefore it will not be in L.
Hence, in both cases, we have shown that no matter how we divide the string s = a^3^p, pumping it will result in a string that does not belong to L. This contradicts the pumping lemma assumption. Therefore, we conclude that L = {a^3^n : n ≥ 0} is not a context-free language.