Given the language $L_n = \{ a^n \}$ for a natural number $n \geq 2$. Is there a symbol minimal context-free grammar $G$ that generates $L_n$ and contains a rule of the form $A \rightarrow aB$ where $A$ and $B$ are non-terminals?


Symbol minimal means that there is no other context-free grammar that generates $L_n$ with fewer characters (symbols) for all rules. For instance, the number of symbols of the rules in $\{ S \rightarrow a, S \rightarrow aS \}$ is 7 (these rules are also minimal for $\{ a \}^+$).

Known Results

Facts about G (a symbol minimal context-free language for $L_n$) that I have already proved:

  • The right hand side of the rules of $G$ consist of at least 2 characters (non-terminals and/or terminals) (otherwise it’s easy to find a grammar that has fewer symbols).
  • For each non-terminal of $G$ there exists exactly one rule (can be shown by contradiction).
  • There are no loops in the derivations of $G$ (because $L_n$ is finite).
  • There is an upper bound for the number of symbols: we can trivially generate $L_n$ with the rules $\{ S \rightarrow a^n \}$. We count the number of symbols and get $n + 2$ – that’s an upper bound.

I wrote a program that finds symbol minimal grammars for a specific $n$ by creating all possible grammars generating $L_n$ (there are only a finite number because we have an upper bound). Here are the results for some small $n$:

  • $n = 2$: $\{ S \rightarrow aa \}$, $4$ symbols
  • $n = 3$: $\{ S \rightarrow aaa \}$, $5$ symbols
  • $n = 7$: $\{ S \rightarrow aaaaaaa \}$, $9$ symbols
  • $n = 8$: $\{ S \rightarrow a^8\}$, $\{ S \rightarrow AA, A \rightarrow a^4 \}$, $\{ S \rightarrow AAAA, A \rightarrow aa \}$, $10$ symbols
  • $n = 9$: $\{ S \rightarrow AAA, A \rightarrow a^3 \}$, $10$ symbols
  • $n = 10$: $\{ S \rightarrow AA, A \rightarrow a^5 \}$, $\{ S \rightarrow A^5, A \rightarrow aa \}$, $\{ S \rightarrow aA^3, A \rightarrow a^3 \}$, $11$ symbols
  • $n = 11$: $\{ S \rightarrow aAA, A \rightarrow a^5 \}$, $\{ S \rightarrow aA^5, A \rightarrow aa \}$, $\{ S \rightarrow aaA^3, A \rightarrow a^3 \}$, $12$ symbols
  • $n = 12$: $\{ S \rightarrow AAA, A \rightarrow a^4 \}$, $\{ S \rightarrow A^4, A \rightarrow aaa \}$, $11$ symbols
  • $n = 13$: …, $12$ symbols
  • $n = 14$: …, $13$ symbols
  • $n = 15$: …, $12$ symbols
  • $n = 16$: …, $12$ symbols

There are nice „ups and downs“ in the number of symbols, right? I have seen grammars that contain rules like $A \rightarrow aB$ but they were not symbol minimal …

  • 7
    $\begingroup$ Your question reminds me of the Addition Chain problem (en.wikipedia.org/wiki/Addition_chain) and I would not be surprised it is was as hard as this problem. $\endgroup$
    – J.-E. Pin
    Sep 15, 2013 at 20:32
  • $\begingroup$ Sorry, but I don’t see how this helps me. Anyway, thanks for Your comment. $\endgroup$
    – Ronny
    Sep 16, 2013 at 11:12
  • $\begingroup$ I think $\Theta(\log n)$ is the size of the minimal system for every $n$. $\endgroup$
    – domotorp
    Sep 16, 2013 at 14:07
  • $\begingroup$ What exactly are you asking for? An efficient decision procedure which takes $n$ as input and outputs the truth of the statement "At least one of the symbol minimal grammars for $L_n$ contains a rule of the desired form"? A proof that at least one $n$ exists for which that statement is true? $\endgroup$ Sep 16, 2013 at 16:42
  • 1
    $\begingroup$ This is great!! I've thought quite a bit about this concept in the past. I've always thought of it as the context-free measure of compressibility for the number n. It's in some sense comparable to kolmogorov complexity, but instead of Turing machines, our programs our CFG's. $\endgroup$ Aug 11, 2017 at 17:25

2 Answers 2


First, let me add some more to the known results section, specific to your question.

  • $B$ must occur in another RHS than $A\rightarrow aB$, or we could just copy the rule that has $B$ on the LHS instead of $B$ to the above rule to get a smaller system.

  • In any other RHS that has $B$, there can be no terminal symbol because instead of $aB$ we could write $A$.

  • $A$ must occur at least $4$ times on the RHS, otherwise, we could just write $aB$ instead of it.

This already shows that $n$ will be quite large that satisfies these. However, I think such an $n$ might exist. Below I give a set of rules for $n=93$ with $28$ symbols and I challenge all to make a smaller system! (If the challenge is too easy, generalize it in the obvious way...)

$S\rightarrow AAAACCC$

$A\rightarrow aB$

$B\rightarrow aaa$

$C\rightarrow DDD$

$D\rightarrow BBB$


Well, this is not optimal for any $n$ as shown by Peter in the comment...

  • 2
    $\begingroup$ $AAAA$ can be replaced by $aBBBBB$ and the rule for $A$ removed to save two symbols. $\endgroup$ Sep 16, 2013 at 16:56
  • $\begingroup$ Thanks @domotorp! The other known results You got are nice. I’ll think about a proof or a counter example with this facts … $\endgroup$
    – Ronny
    Sep 16, 2013 at 20:49
  • $\begingroup$ Can get to 22 symbols: $S \to AAA, A \to aBBB, B \to CC, C \to aaaaa$. $\endgroup$ Jul 20, 2017 at 15:53
  • 1
    $\begingroup$ Now down to 21 symbols: $S \to BBB, B \to aCCCCC, C \to aaaaaa$. $\endgroup$ Jul 20, 2017 at 16:00

Let $c(n)$ be the minimum complexity of any CFG to generate $\{a^n\}$. Here is a useful result:

$c(mn + d) \le c(n) + m + d + 2$ with $0 \le d < n$. Add the rule $S \to aa\cdots aaAA \cdots AA$ where there are $d$ occurrences of $a$ and $m$ occurrences of the original start variable $A$. But for specific values of $m, n$, we can do better:

  • If $m = 9$, we can have $c(9n + d) \le c(n) + 10 + d$ - add the rule $S' \to aa\cdots aaAAA, A \to SSS$ where $S$ is the original start variable.
  • If $m = 10$, a similar construction has $c(10n + d) \le c(n) + 11 + d$.
  • If $m = 12$, a similar construction has $c(12n + d) \le c(n) + 11 + d$.

There seems to be an interesting possible connection between the prime factorization of $n$ here and $c(n)$ by making a program to generate these grammars and inspecting the grammars themselves. For example, $c(10^5) \le 51$, and the grammar generated has 8 variables, of which has RHSes of length 5, 2, 5, 5, 5, 5, 4, and finally 4 terminals. But the prime factorization of $10^5$ is $2^5 \times 5^5 = 2 \times 4^2 \times 5^5$.

  • $\begingroup$ Very cool!! Thanks for sharing this. :) $\endgroup$ Aug 11, 2017 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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