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

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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