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

<ul>
<li><p>$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.</p></li>
<li><p>In any other RHS that has $B$, there can be no terminal symbol because instead of $aB$ we could write $A$.</p></li>
<li><p>$A$ must occur at least $4$ times on the RHS, otherwise, we could just write $aB$ instead of it.</p></li>
</ul>

<p>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...)</p>

<p>$S\rightarrow AAAACCC$</p>

<p>$A\rightarrow aB$</p>

<p>$B\rightarrow aaa$</p>

<p>$C\rightarrow DDD$</p>

<p>$D\rightarrow BBB$</p>

<h1>Update</h1>

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

CC BY-SA 3.0
2013-09-16T16:56:18.730Z
$AAAA$ can be replaced by $aBBBBB$ and the rule for $A$ removed to save two symbols.
Peter Taylor
CC BY-SA 3.0
2013-09-16T20:49:52.180Z
Thanks @domotorp! The other known results You got are nice. I’ll think about a proof or a counter example with this facts …
Ronny
CC BY-SA 3.0
2017-07-20T15:53:13.233Z
Can get to 22 symbols: $S \to AAA, A \to aBBB, B \to CC, C \to aaaaa$.
Ryan Dougherty
CC BY-SA 3.0
2017-07-20T16:00:33.627Z
Now down to 21 symbols: $S \to BBB, B \to aCCCCC, C \to aaaaaa$.
Ryan Dougherty
CC BY-SA 3.0
2013-09-16T14:00:59.643Z
2013-09-16T18:46:31.400Z
2013-09-16T18:46:31.400Z
domotorp
<p>Let $c(n)$ be the minimum complexity of any CFG to generate $\{a^n\}$. Here is a useful result:</p>

<p>$c(mn + d) \le c(n) + m + d + 2$ with $0 \le d &lt; 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:</p>

<ul>
<li>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.</li>
<li>If $m = 10$, a similar construction has $c(10n + d) \le c(n) + 11 + d$.</li>
<li>If $m = 12$, a similar construction has $c(12n + d) \le c(n) + 11 + d$.</li>
</ul>

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

CC BY-SA 3.0
2017-08-11T17:27:37.317Z
Very cool!!  Thanks for sharing this.  :)
Michael Wehar
CC BY-SA 3.0
2017-08-11T14:47:32.310Z
2017-08-11T14:54:54.807Z
2017-08-11T14:54:54.807Z
Ryan Dougherty
<h1>Question</h1>

<p>Given the language $L_n = \{ a^n \}$ for a natural number $n \geq 2$. Is there a <em>symbol minimal</em> 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?</p>

<h1>Remark</h1>

<p><em>Symbol minimal</em> 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 \}^+$).</p>

<h1>Known Results</h1>

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

<ul>
<li>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).</li>
<li>For each non-terminal of $G$ there exists exactly one rule (can be shown by contradiction).</li>
<li>There are no loops in the derivations of $G$ (because $L_n$ is finite).</li>
<li>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.</li>
</ul>

<p>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$:</p>

<ul>
<li>$n = 2$: $\{ S \rightarrow aa \}$, $4$ symbols</li>
<li>$n = 3$: $\{ S \rightarrow aaa \}$, $5$ symbols</li>
<li>…</li>
<li>$n = 7$: $\{ S \rightarrow aaaaaaa \}$, $9$ symbols</li>
<li>$n = 8$: $\{ S \rightarrow a^8\}$, $\{ S \rightarrow AA, A \rightarrow a^4 \}$, $\{ S \rightarrow AAAA, A \rightarrow aa \}$, $10$ symbols</li>
<li>$n = 9$: $\{ S \rightarrow AAA, A \rightarrow a^3 \}$, $10$ symbols</li>
<li>$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</li>
<li>$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</li>
<li>$n = 12$: $\{ S \rightarrow AAA, A \rightarrow a^4 \}$, $\{ S \rightarrow A^4, A \rightarrow aaa \}$, $11$ symbols</li>
<li>$n = 13$: …,  $12$ symbols</li>
<li>$n = 14$: …,  $13$ symbols</li>
<li>$n = 15$: …,  $12$ symbols</li>
<li>$n = 16$: …,  $12$ symbols</li>
</ul>

<p>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 …</p>

CC BY-SA 3.0
2013-09-15T20:32:11.547Z
Your question reminds me of the Addition Chain problem (http://en.wikipedia.org/wiki/Addition_chain) and I would not be surprised it is was as hard as this problem.
J.-E. Pin
CC BY-SA 3.0
2013-09-16T11:12:38.110Z
Sorry, but I don’t see how this helps me. Anyway, thanks for Your comment.
Ronny
CC BY-SA 3.0
2013-09-16T14:07:32.733Z
I think $\Theta(\log n)$ is the size of the minimal system for every $n$.
domotorp
CC BY-SA 3.0
2013-09-16T16:42:13.860Z
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?
Peter Taylor
CC BY-SA 3.0
2013-09-16T20:38:25.987Z
It would be fine to get a concrete symbol minimal context-free grammar that generates $L_n$. But this seems to very hard. What I want to know is: Is there some $n$ so that a symbol minimal context-free grammar generating $L_n$ contains a rule like $A \rightarrow aB$? (I want to have a proof.)
Ronny
CC BY-SA 3.0
2017-08-11T17:25:20.597Z
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.
Michael Wehar
CC BY-SA 3.0
2017-08-11T17:26:22.837Z
Someday, we should talk about this more as there are several relevant problems.  :)
Michael Wehar
<fl.formal-languages><optimization><context-free>
Investigation of Symbol Minimal Context-Free Grammars for the Language $a^n$
Ronny
# Investigation of Symbol Minimal Context-Free Grammars for the Language $a^n$

(Asked by: username_0 on 2013-09-15)

# 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 …

**Tags:** fl.formal-languages, optimization, context-free
> **Comments:**
> **username_1**: Your question reminds me of the Addition Chain problem (http://en.wikipedia.org/wiki/Addition_chain) and I would not be surprised it is was as hard as this problem.  
> **username_0**: Sorry, but I don’t see how this helps me. Anyway, thanks for Your comment.  
> **username_2**: I think $\Theta(\log n)$ is the size of the minimal system for every $n$.  
> **username_3**: 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?  
> **username_0**: It would be fine to get a concrete symbol minimal context-free grammar that generates $L_n$. But this seems to very hard. What I want to know is: Is there some $n$ so that a symbol minimal context-free grammar generating $L_n$ contains a rule like $A \rightarrow aB$? (I want to have a proof.)  
> **username_4**: 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.  
> **username_4**: Someday, we should talk about this more as there are several relevant problems.  :)  

---

## 2 answers

### Answer by username_2 on 2013-09-16. Score: 4

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

> **Comments:**
> **username_3**: $AAAA$ can be replaced by $aBBBBB$ and the rule for $A$ removed to save two symbols.  
> **username_0**: Thanks @domotorp! The other known results You got are nice. I’ll think about a proof or a counter example with this facts …  
> **username_5**: Can get to 22 symbols: $S \to AAA, A \to aBBB, B \to CC, C \to aaaaa$.  
> **username_5**: Now down to 21 symbols: $S \to BBB, B \to aCCCCC, C \to aaaaaa$.  

---

### Answer by username_5 on 2017-08-11. Score: 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$.

> **Comments:**
> **username_4**: Very cool!!  Thanks for sharing this.  :)  

---

