Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
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?

Asked By : Vasilis Manavis

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.

Comments:

  1. In terms of number of symbols, a grammar based on powers of 2 is the most efficient.
  2. This approach seems (at first) to work only for powers of 2, but in fact you can use the binary representation to handle any upper bound (exercise).
Best Answer from StackOverflow

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

 Ask a Question

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback