1
$\begingroup$

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$
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".

| cite | improve this answer | |
$\endgroup$

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