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

Problem Detail: 

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.

Asked By : Dimitris Sfounis

Answered By : Terence Hang

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

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, i.e. $uv^2wx^2y\notin L$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47137

 Ask a Question

 Download Related Notes/Documents