When we speak of a variable, sometimes we will mean the string it expands to, and other times, the variable itself. Let $t \leqslant s$ mean substring.

Take the string $s = a^6$. Then its compressible substrings are $aa, aaa$. Now assign positioned variables $A_i \to aa$, $B_j \to aaa$, for $i = 1...5, j = 1...4$ like this:

 A1  A3
___ ___  ...
a a a a a a 
  ___   ...
 B1     B4
_____ _____
a a a a a a
    B2   ...

Place each positioned variable in a graph vertex, and connect two vertices whenever one variable cuts another variable, i.e. $A_1 \leqslant B_1$ has a proper substring relationship, so there's no cut there, however, $A_1$ and $B_2$ cut each other, because they overlap in this way:

$$ \exists v \leqslant s : \\ A_1 u = v = u'' B_1; \\ |u|, |u''| \gt 0 $$

      /```/```\    \
    | __/  \ _/\__   |
    |/     /\____ \_/_
    /\____/__  __\_/  \
   /     /   \/   \    \

An undirected edge between two nodes means their respective variables cut one another (the positioned strings they expand to within $s$)

Now, you start by picking any vertex of least degree - i.e. the least number of cuttings of other variables. Here, the choices are one of: $B_1, B_4, A_1, A_5$. However, $A_1 \leqslant B_1$ so choosing $A_1$ before $B_1$ is preferable, because, if you do this, then you can still choose $B_1$ later and have $A_1$ sit inside of the rule $B_1 \to A_1 a$ like so. So the first choices are merely $A_1, A_5$.

So you loop over the first choices, say we chose $A_1$. This gives:

$$g :\\ S \to Aa^4 \\ A \to aa $$

And the conflict graph then becomes:

      \       |  __/
       \       \/______
         \     /       \

You then have choices: $B1, B_4, A_4, A_5$ since choosing $A_1$ the first iteration, cancelled the nodes $A_2, B_2$ (and their edges).

Now loop over the possible choices, and so on...

Question. Does this always lead to all possible smallest grammars for $s$?

  • $\begingroup$ It's called maximal choice because at each stage, we leave the maximal number of choices for the next stage. $\endgroup$ Nov 12, 2022 at 23:32
  • $\begingroup$ I would like to compute the exact smallest grammars, then compare the output to this algorithm however, I can't find any exact smallest grammar algorithm on the internet. I don't want to make some naive brute-force one, because it would take minutes for small strings, so I couldn't compare very many examples. Anyone know of a fast enough exact algorithm? $\endgroup$ Nov 12, 2022 at 23:41
  • $\begingroup$ Also note that for this small example, the grammar doesn't grow complex enough to be interesting. When it does, you simply create a new conflict graph for each grammar, where positioned variables are now $A^B_i$ i.e. the $i$th occurence of $A$ within the rule $B \to \beta$. You then get several disjoint component subgraphs, one component for each rule in your built-up grammar. $\endgroup$ Nov 12, 2022 at 23:44


Your Answer

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