# Context-free grammar for $L = \{a^{2^k}, k \in\mathbb{N}\}$

In an exercise, I am asked to find a context free grammar for language $L = \{a^{2^k}, k \in \mathbb{N}\}$.

I have been trying to use a "doubling" variable. If $a^{2n} \in L, n\in\mathbb{N}$ then use this variable to double the $a$'s that have been produced by the other language rules.

Is this thinking valid? So far I haven't been able to get anywhere with it, but it seems logical given the double-stack of powers.

$L = \{a^{2^k}, k \in \mathbb{N}\}$ is not a context-free language according to Pumping lemma for context-free languages.

Suppose $L$ is context-free. The pumping lemma says there exists some integer $p \ge 1$ such that every string $s$ in $L$ where $|s| \ge p$ can be written as $s=uvwxy$ where $|vwx|\le p$, $|vx|\ge 1$ and $uv^nwx^ny$ is in $L$ for all $n \ge 0$.

Let $s$ be a string in $L$ longer than $p$, and $u$, $v$, $w$, $x$, and $y$ have the properties given by the pumping lemma. Thus $uwy, uvwxy, uv^2wx^2y\in L$. Let $a$ and $b$ be such that $$|uwy|=2^a, |uvwxy|=2^b$$ Note $b>a$. Then $$|uv^2wx^2y|=2|uvwxy|-|uwy| = 2^{b+1}-2^a = 2^a(2^{b+1-a}-1)$$ But $2^a(2^{b+1-a}-1)$ is not a power of 2, and so $uv^2wx^2y\notin L$.

• This is part of an exercise, therefore highly unlikely that it would ask of a context free grammar on context free Language. Maybe I'm translating it incorrectly? The exercise asks for a "grammar without restrictions (rewrite system)", which I assumed is a context-free grammar. – Dimitris Sfounis Sep 13 '15 at 20:27
• @DimitrisSfounis No context-free grammar exists for non context free language. By "grammar without restrictions" you mean unrestricted grammar? That's grammar for recursively enumerable language, know n as type-0 languages. – Terence Hang Sep 13 '15 at 23:14
• To add to what's been said, an unrestricted grammar for your language is a fairly common example. Do a little bit of digging and it'll turn up. – Rick Decker Sep 13 '15 at 23:16

Your approach does not work: you can't force all the variables to "double" at once using only context-free rules.

As the other answers show, your effort is futile: $L$ is not context-free, so there can be no such grammar.

For reference, context-sensitive rules allow you to control the "doubling". Idea: move markers through the sentence; only with the marker can doubling rules be applied. A second marker triggers termination.

Try for yourself to translate this idea into a grammar!

No luck? here goes:

\qquad\begin{align*} S &\to \ A \$\\ \$ A &\to \$\bullet A \mid \circ A \\[1ex] \bullet A &\to AA \bullet \\ \bullet \$ &\to \$\\[1ex] \circ A &\to a \circ \\ \circ \$ &\to \varepsilon\end{align*}$Note: • The first rule sets up end markers. • The second rule(s) spawn the two markers; only one$\circ$can be spawned! • Markers can only move to the right, and are absorbed by the last end marker. • Markers can not overtake each other. I'll leave a formal proof of correctness as an exercise; see here for some ideas. Hint: Each marker is a "phase"; you have$k-1\bullet$-phases that generate$A^{2^k}$, then a single$\circ$-phase that translates all$a$into$A$. A language which is a subset of$a^*$is known as a unary language. There is a complete classification of unary languages which are context-free. In particular, if$L$is a unary language then the following are equivalent: 1.$L$is context-free. 2.$L$is regular. 3. There exists$m$such that$a^n \in L$iff$a^{n+m} \in L$. 4. There exist$m_1,m_2$and subsets$S_1 \subseteq [m_1],S_2 \subseteq [m_2]$such that$a^n \in L$iff$n \in S_1$or$n-m_1-rm_2 \in S_2$for some integer$r \geq 0\$.