# Context-free grammar for $L = \{a^n : n\leq2^{20}\}$

I want to find a context-free grammar for $L = \{a^n : n\leq2^{20}\}$. There's one for sure. I approached it by two ways and both seemed dead end. One was to set a limit during the production of the new strings. But I don't think there's such a thing in CFGs. Second approach was to produce the strings of the language top-down. Starting from the last string $a^{2^{20}}$ and removing an $a$ each time till epsilon but I don't think that's achievable either. Any ideas?

• There's got to be some kind of a trick to it that has to do with some SPECIAL property of that number 2^20. So I looked it up in wolfram alpha: wolframalpha.com/input/?i=1048576 Turns out that number, for one of many reasons, is special because it is a perfect power. Let me think about it a little more. – alvonellos Mar 8 '14 at 16:51
• Think of one that produces $a^*$, then prepend $a^{2^{20}}$ to the first production. – G. Bach Mar 8 '14 at 16:51
• @G.Bach 1st approach just needs a limiter to 2^20 # of 'a'. Nit sure what you mean – Vasilis Manavis Mar 8 '14 at 16:59
• Can you come up with a grammar for $\{a^n:n\leq 5\}$? How is $2^{20}$ different? – Karolis Juodelė Mar 8 '14 at 17:01
• Sorry, I misread the question; I thought it said $n \geq 2^{20}$. – G. Bach Mar 8 '14 at 17:09

As Karolis mentions, one solution is $$S \to \epsilon | a | a^2 | a^3 | \cdots | a^{2^{20}}.$$ However, we can do better: \begin{align*} &A_{20} \to A_{19} A_{19} \\ &A_{19} \to A_{18} A_{18} \\ &A_{18} \to A_{17} A_{17} \\ &A_{17} \to A_{16} A_{16} \\ &A_{16} \to A_{15} A_{15} \\ &A_{15} \to A_{14} A_{14} \\ &A_{14} \to A_{13} A_{13} \\ &A_{13} \to A_{12} A_{12} \\ &A_{12} \to A_{11} A_{11} \\ &A_{11} \to A_{10} A_{10} \\ &A_{10} \to A_9 A_9 \\ &A_9 \to A_8 A_8 \\ &A_8 \to A_7 A_7 \\ &A_7 \to A_6 A_6 \\ &A_6 \to A_5 A_5 \\ &A_5 \to A_4 A_4 \\ &A_4 \to A_3 A_3 \\ &A_3 \to A_2 A_2 \\ &A_2 \to A_1 A_1 \\ &A_1 \to A_0 A_0 \\ &A_0 \to a | \epsilon \end{align*} The start symbol is $A_{20}$. You can prove by induction that $A_k$ generates $\{ a^n : n \leq 2^k \}$. If you want an even shorter solution, you can try \begin{align*} &A_{20} \to A_{18} A_{18} A_{18} A_{18} \\ &A_{18} \to A_{16} A_{16} A_{16} A_{16} \\ &A_{16} \to A_{14} A_{14} A_{14} A_{14} \\ &A_{14} \to A_{12} A_{12} A_{12} A_{12} \\ &A_{12} \to A_{10} A_{10} A_{10} A_{10} \\ &A_{10} \to A_8 A_8 A_8 A_8 \\ &A_8 \to A_6 A_6 A_6 A_6 \\ &A_6 \to A_4 A_4 A_4 A_4 \\ &A_4 \to A_2 A_2 A_2 A_2 \\ &A_2 \to \epsilon|a|aa|aaa|aaaa \end{align*} Many more options are possible, see which one you like most.
• Well, $2^{20}$ is also an integral power of $4$, of $16$, of $32$, and of $1024$: $2^{20} = 4^{10} = 16^5 = 32^4 = 1024^2$. The most economical grammar (in terms of number of symbols) is the one based on powers of 2. – Yuval Filmus Mar 9 '14 at 0:18