Unrestricted grammar for the language of strings whose length is not $2^n$
Your method is correct to generate $L$. But if you change the rule to $0a \to a^k0$ then the language you generate is $L^{'}=\{a^k,a^{k^2},a^{k^3}....\}$ ( $k &gt;2$) .
You can show that language $L$ is indeed decidable. One way is to give an algorithm that halts on every input in $\sum^{*}$ and gives the correct result. Following is the approach

(1) If the input is empty reject. 
(2) If not empty , check if there are even number of 'a' or odd. If only one 'a' is there accept. If odd 'a' ( > 1 ) are there reject. 
(3) If even 'a' are there, go back to starting of input and cross off alternate 'a' from beginning to end of input. Go back to step (2).
The algorithm accepts the string $a$ in addition. You can always modify the above algorithm, keeping a special check that if the input is 'a' reject.