As part of a Computation Theory exercise, I am asked to find a context free language for the language L = a^(2^k).
How I tried tackling it: I want to work with an X sentence that recursively doubles all the a's that were produced by other sentences. That will lead me only to strings like a, a^2, a^4, a^8 which is the grammar I'm looking for.
But is such a thing possible? How can I do this?
S -> aS | X | ε
Χ -> (doubles all previous a's)
And there is also the problem of doubling a string of as that would yield a number of as not accepted by the a^(2^k) condition, for example a^3, a^5, a^6 all fall "in-between" the progression gaps of a^(2^k).
Consider the string a^(2^p) in your language, where p is the constant in the pumping lemma for context-free languages. We can write this string as uvxyz such that:
|vy| >= 1|vxy| <= pThen we know that if the language is context free, then all strings of the form u v^n x y^n z should be in the language for n >= 0. Let's call a = |uxz| and b = |vy|. Then we must have strings in the language of length a, a + b, a + 2b, .... Suppose a = 2^k is a power of 2 and that a + b is also a power of 2. Then b = 2^m - 2^k and a + 2b = 2^(m+1) - 2^k = 2^j is also a power of 2. Rewrite this as 2^(m+1) = 2^k + 2^j. Divide through by the smaller of k and j to get 2^r = 2^s + 1. The only way this equation can be satisfied is if s = 0, that is, if k = j, since otherwise the RHS is odd while the LHS must be even. But then m = k also and b = 0. But b must be greater than 0, by the pumping lemma.
Man that was ugly but you get the idea.