# The maximal choice smallest grammar algorithm. Is this an exact algorithm or an approximation?

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

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

           /\
//\    \
B1---B2---B3----B4
| __/  \ _/\__   |
|/     /\____ \_/_
/\____/__  __\_/  \
/     /   \/   \    \
A1----A2---A3---A4---A5


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:

    B1--------B3----B4
\       |  __/
\       \/______
\     /       \
--A3---A4---A5
`

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

• It's called maximal choice because at each stage, we leave the maximal number of choices for the next stage. Nov 12, 2022 at 23:32
• 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? Nov 12, 2022 at 23:41
• 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. Nov 12, 2022 at 23:44