1
$\begingroup$

This question already has an answer here:

I was trying to find a cf-grammar for $L = \{a^{2^n}| n \geq 1\}$ but I cannot seem to find one. Is there a cf-grammar or does it not exist because of the quadratic-exponent?

$\endgroup$

marked as duplicate by J.-E. Pin, David Richerby, Discrete lizard, Evil, Yuval Filmus formal-languages Jun 6 '18 at 17:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

It's a more or less standard result that the language in question isn't context-free, so the answer to your question is no. The same holds for a number of similar languages, like $$ L_1= \{a^{n^2} \mid n\ge 0\}\quad\text{and}\quad L_2=\{a^p\mid p\text{ is prime}\} $$ There's a nice property that can be useful in cases like this: any context-free language over a one-symbol alphabet is regular. This, combined with a characterization of regular languages over a unary alphabet implies that languages like the ones above cannot be context-free since they're too "sparse".

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.