3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – alvonellos Mar 8 '14 at 16:51
  • $\begingroup$ Think of one that produces $a^*$, then prepend $a^{2^{20}}$ to the first production. $\endgroup$ – G. Bach Mar 8 '14 at 16:51
  • $\begingroup$ @G.Bach 1st approach just needs a limiter to 2^20 # of 'a'. Nit sure what you mean $\endgroup$ – Vasilis Manavis Mar 8 '14 at 16:59
  • 2
    $\begingroup$ Can you come up with a grammar for $\{a^n:n\leq 5\}$? How is $2^{20}$ different? $\endgroup$ – Karolis Juodelė Mar 8 '14 at 17:01
  • $\begingroup$ Sorry, I misread the question; I thought it said $n \geq 2^{20}$. $\endgroup$ – G. Bach Mar 8 '14 at 17:09
6
$\begingroup$

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).
$\endgroup$
  • $\begingroup$ What a beautiful grammar. $\endgroup$ – alvonellos Mar 8 '14 at 17:20
  • $\begingroup$ The shorter version is more suitable for power of 4 I think $\endgroup$ – Vasilis Manavis Mar 8 '14 at 17:22
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 9 '14 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.