Skip to main content
1 of 3

$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, then there exists some integer $p \ge 1$, that every string s in L that $|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$

From definition, $|s|=2^k$ for some $k\in\mathbb{N}$, but $|uv^nw^nx|=|uwx|+n*|vx|$. Suppose $$|uwx|=2^a, |uvwxy|=2^b (b>a)$$ then $$|uv^2wx^2y|=2|uvwxy|-|uwx| = 2^{b+1}-2^a = 2^a(2^{b+1-a}-1)$$ is not a power of 2. ie. $uv^2wx^2y\notin L$.