Context-free grammar for language L = a^(2^k)

0
votes

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).

1
context-free-grammarcomputation-theory
This might be rather suited for the CS SE. – Kyll
see en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages. Consider k such that 2^k > p... – Chris Dodd
No dice, how can I incorporate it through P? – Dimitris Sfounis

1 Answers

2
votes

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| <= p

Then 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.