Investigation of Symbol Minimal Context-Free Grammars for the Language $a^n$

Question

Question

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?

Remark

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 …

Answer 1

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$

Update

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

Answer 2

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$.