6
$\begingroup$

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 …

$\endgroup$
  • 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 '13 at 20:32
  • $\begingroup$ Sorry, but I don’t see how this helps me. Anyway, thanks for Your comment. $\endgroup$ – Ronny Sep 16 '13 at 11:12
  • $\begingroup$ I think $\Theta(\log n)$ is the size of the minimal system for every $n$. $\endgroup$ – domotorp Sep 16 '13 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$ – Peter Taylor Sep 16 '13 at 16:42
  • $\begingroup$ 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.) $\endgroup$ – Ronny Sep 16 '13 at 20:38
3
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ $AAAA$ can be replaced by $aBBBBB$ and the rule for $A$ removed to save two symbols. $\endgroup$ – Peter Taylor Sep 16 '13 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 '13 at 20:49
  • $\begingroup$ Can get to 22 symbols: $S \to AAA, A \to aBBB, B \to CC, C \to aaaaa$. $\endgroup$ – Ryan Jul 20 '17 at 15:53
  • 1
    $\begingroup$ Now down to 21 symbols: $S \to BBB, B \to aCCCCC, C \to aaaaaa$. $\endgroup$ – Ryan Jul 20 '17 at 16:00
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Very cool!! Thanks for sharing this. :) $\endgroup$ – Michael Wehar Aug 11 '17 at 17:27

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.