## 6 Non-Uniqueness of Smallest Grammar and Structure Discovery
### An Empirical Analysis  
We will now introduce a way of measuring the difference between any pair of grammars taken from \(\mathcal{G}_{Q}\). Our measure is based on the fact that our grammars have a single string in their language and that string has only one derivation tree. Therefore it seems natural to use a metric that is commonly used to compare parse trees, such as Unlabeled Brackets \(F_{1}\)[24](also see [25] for a different explanation) in order to compare different grammars (hereafter \(UF_{1}\)). Summarizing the definition, the \(UF_{1}\) measures the overlap of the _brackets_ sets of two parse trees. Given a grammar with a single string \(s\) in its language (which is equivalent to a parse tree) the set of _brackets_ for that grammar is defined as the pairs of indexes in string \(s\) for which there is a non-terminal symbol that expands to that position. For instance, the initial symbol \(S\) of a grammar expands to \(s\), so \((0,|s|-1)\) belongs to the bracket set of that grammar. Full overlap of the brackets sets (\(UF_{1}=1\)) implies that the two smallest grammars are equal, and the converse also holds: if two smallest grammars are equal then \(UF_{1}=1\). Also, given two smallest grammars over the same fixed constituent set, the opposite may happen. Consider again the sequence \(s_{k}=(aba)^{k}\), as defined in Proposition 3, and take \(G_{1}\) as the grammar that rewrites every \(aba\) as \(aA\) while grammar \(G_{2}\) rewrites it as \(Ba\). \(G_{1}\) and \(G_{2}\) do not share any brackets, so \(UF_{1}(G_{1},G_{2})=0\). In our experiments we will use \(UF_{1}\) as the way to compare structure between different smallest grammars. Propositions 2 and 3 suggest that there are sequences for which the number of smallest grammars and the number of grammars for a given set of constituents are both exponential. Both results are based on sequences that were especially designed to show these behaviours. But it might be the case that this behaviour does not occur \"naturally\". In order to shed light on this topic we present four different experiments. The first is directly focused on seeing how Proposition 3 behaves in practice and consists in computing the number of grammars with smallest size that are possible to build using the set of constituents found by the ZZ algorithm. The other three experiments analyze how different all these grammars are. Firstly, we compare the structure of different grammars randomly sampled from the set of possible grammars. Then we compare structure, as in the previous experiment, but this time, the used metric discriminates by the length of the constituents. Finally, we consider in how many different ways a single position can be parsed. The first experiment provides evidence supporting the idea of Proposition 3 being the general rule more than an exceptional case. The second group of experiments suggests that there is a common structure among all possible grammars. In particular, it suggests that longer constituents are more stable than shorter ones and that, if for each position we only consider the longest bracket that englobes it, then almost all of these brackets are common between smallest grammars. All these experiments require a mechanism to compute different grammars sharing the same set of constituents. We provide an algorithm that not only computes this but also computes the total number of grammars that are possible to define for a given set of constituents. Let \(s\) be a sequence, and let Q be a set of constituents. An _MGP-graph_ is a subgraph of the _GP-graph_ used in Section 4.1 for the resolution of the MGP problem. Both have the same set of nodes but they differ in the set of edges. An edge belongs to an _MGP-graph_ if and only if it is used in at least one of the shortest path from node \(0\) to node \(n+1\) (the end node).