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, ninmathbb{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 $kinmathbb{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^2ynotin L$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/47137 Ask a Question Download Related Notes/Documents
