Cheap and Secure Web Hosting Provider : See Now

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

, ,
Problem Detail:

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?

#### Answered By : Yuval Filmus

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.