

\section{Supplementary Material for the Demonstration}\label{app:bio}
We implemented our algorithm within a tool called PCFGLearner. The code and the data-sets used in this section, as well as a manual explaining how to employ our tool, are available with the submitted supplementary material. In this section we apply PCFGLearner to the learning of two PCFGs over genomic data. 

The section starts with a description of how the string data-set was generated (Section \ref{app:methods}).
Then, the conversion of the strings to parse trees is described in Section \ref{supp:trees}. 
\commentout
{
we generate a parse-tree for each sequence, using a variation of the CKY algorithm \cite{younger1967recognition,kasami1966efficient} as detailed in App.~\ref{supp:trees}, and assign it a probability according to its relative number of occurrences in the data-set.} 
Next, the implementation details of the oracle are given: Section \ref{supp:editDist} describes how the $\query{smq}$ was implemented, and Section \ref{supp::randomSEQ} describes how the $\query{seq}$ was implemented. 
A biological interpretation of the first grammar is given in Section \ref{supp:biogramm}, and the description of the second grammar is given in Section \ref{supp:bioFimACD}.

\subsection{Methods and datasets}\label{app:methods}
Genes in our experiment are represented by their membership in Clusters of Orthologous Genes (COGs) \cite{tatusov2000cog}.
$1,487$ fully sequenced prokaryotic strains with COG ID annotations were downloaded from GenBank (NCBI; ver 10/2012). The gene clusters were generated using the tool CSBFinder-S \cite{csbfinder-s}.

CSBFinder-S was applied to all the chromosomal genomes in the dataset after removing their plasmids, using parameters $q=1$ (a colinear gene cluster is required to appear in at least one genome) and $k=0$ (no insertions are allowed in a colinear gene cluster), resulting in 595,708 colinear gene clusters.  Next, ignoring strand and gene order information, colinear gene clusters that contain the exact same COGs were united to form the generalized set of gene clusters.

To generate the trees for the first example, a subset of strings over the COGs AcrA(COG0845), AcrB(COG0841), TolC(COG1538) and AcrR(COG1309), where each of these COGs appeared at least once, was considered. This yielded 415 instances over 11 distinct strings. After the removal of strand information, 7 distinct strings remained, from which the trees were constructed. 

To generate the trees for the second example, a subset of strings over the COGs FimA(COG3539), FimC(COG3121), FimD(COG3188), and CitB(COG2197) was considered. This yielded 1899 instances over 28 distinct strings. After the removal of strand information, 25 distinct strings remained, from which the trees were constructed. 

In both examples, the constructed trees were annotated with a probability, according to the frequency of the corresponding strings in the dataset.  For the sake of simplicity and efficiency, we used binary trees in the given examples.

\subsection{Tree construction}\label{supp:trees}
Since the gene-cluster-data is available as strings, and our learning algorithm accepts trees, we propose the following approach to construct the expected parse trees from the strings by modelling two of the main events in operon evolution: in-tandem gene duplications~\parciteauthor{lewis1951pseudoallelism,labedan1995widespread} and progressive merging of sub-operons~\parciteauthor{fani2005origin,fondi2009origin}.

To model the former event, if two homologous genes (represented by the same COG) are found next to each other across many genomes, we assume that this is a result of a duplication event, and we place these two genes in the same sub-tree.
To model the latter event, we assume that if a sub-string is significantly over-represented in our data-set (indicating that it is conserved across many bacteria), then it is likely that this sub-string encodes a conserved functional unit, and that it should be confined to a distinguished sub-tree. 

The following scoring measure is used by the proposed parser to represent how likely it is that a considered parse tree structurally interprets a string.
For a given string $s$, let $s[i]$ be the $i$'th character in the string, and let $s[i:j]$ be the sub-string from the $i$'th character to the $j$'th character.
\commentout
{For every $i$ let $M_{i}$ be the maximal sub-string to which $S[i]$ belongs, in which all the characters are identical. 
First we define a \textbf{violating} sub-string, as a sub-string $s[i:j]$ in which there exists $i\leq k\leq j$ s.t $M_{k}\nsubseteq s[i:j]$. 

A \textbf{valid} parse-tree is an unlabeled derivation tree, whose yield is non-violating, and in which every non-leaf node can either have exactly two non-leaf children, or all of his children are leaves. In the latter case we denote such a node as a \textit{sub-string node}.
}

Given a weight function $w:\Sigma^{*}\rightarrow \mathbb{R}^{+}$, for a given string $s=\sigma_{1}\sigma_{2}...\sigma_{n}$, let $w_{\textsl{tree}}(s)$ denote the following function:
\[
 w_{\textsl{tree}}(s) = 
  \begin{cases} 
   w(s) &\text {if } |s|\leq 2 \\
 \begin{split}
   w(s)+\max_{1\leq i\leq n} (&w_{\textsl{tree}}(s[1:i])+\\
   &w_{\textsl{tree}}(s[i+1:n]))\end{split}  &\text { otherwise}\\
  \end{cases}
\]
\commentout
{
Let $s$ be a string of length $n$. And let $1\leq i,j\leq n$. We denote by $\mathcal{T}[i,j]$ the set of all possible valid parse trees over the string $s[i:j]$. Let us mark by $\textsl{OPT}[i,j]$ the maximal weight of a tree in $\mathcal{T}[i,j]$ that is:
\begin{equation*}
    \textsl{OPT}[i,j]=\max_{t\in\mathcal{T}[i,j]} w(t)
\end{equation*}
Clearly we have:
\begin{equation*}
    \begin{split}\textsl{OPT}[i,j]=
        \max(&w(S[i:j]),\max_{i\leq k<j} \textsl{OPT}[i,k]+\\
        &\textsl{OPT}[k+1,j]+w(S[i:j]))
    \end{split}
\end{equation*}
}
The optimal score $w_{\textsl{tree}}(s)$, as well as a corresponding optimal tree, can now be computed in $O(n^{3})$ using a simple dynamic-programming algorithm, which is a variation of the CKY algorithm \cite{kasami1966efficient, younger1967recognition}.

To force consecutive runs of a gene to appear together, the string $s$ is pre-processed before applying the algorithm. For each $\sigma\in\Sigma$, consecutive runs of $\sigma^{k}$ are merged to a new symbol $\sigma_{k}$. The new symbol $\sigma_{k}$ doesn't appear in $s$, and maintains that $w(u\sigma v)=w(u\sigma_{k} v)$ for every $u,v\in\Sigma^{*}$. 

After computing the optimal tree for the pre-processed string, every leaf whose label is $\sigma_{k}$ is replaced by a right-chain (defined in the next section) containing exactly $k$ leaves tagged with $\sigma$.

The tree construction algorithm is used both during the conversion of sequences to trees, as well as during the execution of an equivalence query of the MDR experiment (see section~\ref{supp::randomSEQ}). 

The scoring $w:\Sigma^{*}\rightarrow\mathbb{R}$ is implemented according to  \cite{svetlitsky2019csbfinder}, and we refer the reader to that paper for a detailed elaboration on how it is computed.  In a nutshell, for a given string $s$, and a given dataset $G$, let $q_s$ denote the number of genomes from $G$ in which $s$ occurs.  Assuming a uniform random order of genes in a genome, the ranking score computation first evaluates how likely it is for $s$ to occur in at least $q_s$ genomes from $G$ by mere chance, and then reports the negative logarithm (base $e$) of the computed score, so that the higher the ranking score of $s$, the less likely to be formed merely by chance.  The parameters considered in the ranking score computation for $s$ include the number of input genomes in $G$, the average length of a genome, the length of $s$, the number of genomes from $G$ in which $s$ occurs, and the frequencies of each gene from $s$ in the data. 


\commentout{
\begin{algorithm} [H]
			\begin{algorithmic}[1]
			    \STATE $A \gets \text{empty matrix of size } n\times n$
                \FOR {$d\gets 0$ to $n$}
                \FOR {$i\gets 0$ to $n-d$}
                \STATE $j \gets i+d$
                \STATE $A[i][j] \gets w(S[i:j])$ 
                \FOR {$k\gets i$ to $j$}
                \IF {$A[i][k]+A[k+1][j]>A[i][j]$}
                \STATE $A[i][j] \gets A[i][k]+A[k+1][j]$
                \ENDIF
                \ENDFOR
                \ENDFOR
                \ENDFOR
			\end{algorithmic}
		\caption{$\text{FindOptimalParse}(S,w)$}\label{alg:parse}
\end{algorithm}}
\subsection{Membership query implementation}\label{supp:editDist}
In this section we describe the edit-distance functions that were used in the implementation of the oracle, for $\query{smq}$ computation. We assume that all trees here are binary, and that their labels are in $\mathbb{N}$. We  use the notation $l(t)$ for the label of the tree $t$.

For a tree $t$, if $t$ is not a leaf, let $t_{1}$ and $t_{2}$ be its left and right children, respectively.

Two trees $t,s$ are \emph{incompatible} if $t$ and $s$ are both leaves, and $l(t)\neq l(s)$, or if only one of $t,s$ is a leaf, while the other is an internal node. 

\subsubsection{Swap-Event-Counting Edit Distance}
The swap-event-counting edit distance measure $w(t,s)$ is computed using the following recursive formula:
\[
 w(t,s) = 
  \begin{cases} 
   0 &\text {if } t \text{ and } s \\
           &\text{are leaves and }\\
           &l(t)=l(s) \\
   \infty &\text {if } t \text{ and } s \\
           &\text{are incompatible }\\
 \begin{split}
   \min(&w(t_{1},s_{1})+w(t_{2},s_{2}),\\
   &w(t_{1},s_{2})+w(t_{2},s_{1})+1)\end{split}  &\text { otherwise}\\


  \end{cases}
\]
\subsubsection{Duplication-Event-Counting Edit Distance}
A tree $t$ is a right-chain if $t$ is a leaf, or if the left child of $t$ is a leaf, the right child of $t$ is a right-chain and the labels on all the leaves of $t$ are equal. (Symmetrically, for a left-chain.) 

For a right or left chain $t$, let $\textsl{size}(t)$ be the number of leaves of $t$, and let $\textsl{label}(t)$ be the tagging of the leaves of $t$. (Note that in a chain, all the leaves have the same tagging, so $\textsl{label}$ is well-defined.)

Two trees $t$ and $s$, are \emph{right-chain-homologous}, if both are right-chains with the same tagging. For two chain-homologous trees, we say that $|\textsl{size}(t)-\textsl{size}(s)|$ is the \emph{copy-number difference} between them. 
For two trees $t$ and $s$, we say that $t$ and $s$ are \emph{right-homologous} if either $t$ and $s$ are right-chain-homologous, or if $t=(t_{1},t_{2})$, $s=(s_{1},s_{2})$ and both $t_{1}$ and $s_{1}$, and $t_{2}$ and $s_{2}$ are right-homologous. In that case, the copy-number difference between $t$ and $s$ is the sum of the copy-number differences between $t_{1}$ and $s_{1}$, and $t_{2}$ and $s_{2}$. (Symmetrically, for left-homologous trees.)

For two given trees $t,s$, let $w(t,s)$ denote the duplication-event-counting measure. The value of $w(t,s)$ is the copy-number difference between $t$ and $s$ if they are right-homologous, or $\infty$ if they aren't. The choice of right-homologous instead of left-homologous is arbitrary. 

\[
 w(t,s) = 
  \begin{cases} 
   |\textsl{size}(t)-\textsl{size}(s)| &\text {if } s \text{ and } t \text{ are}\\
                                       &\text{right-chain-homologous}\\
   \infty &\text{if } s \text{ and } t \text{ are incompatible}\\
          &\text{and aren't}\\
          &\text{right-chain-homologous}\\
   w(t_{1},s_{1})+w(t_{2},s_{2}) & \text {otherwise}\\
  \end{cases}
\] 
\commentout
{
$d(t,s)$ would be the copy-number difference between the trees, assuming that $t$ and $s$ are right-chain-homologous. It would be $\infty$ if one of the trees $t,s$ is not a right chain, or if both are right chains but with different labels. And would be the copy-number difference in the number of leaves between them if both are right chains with the same tagging. Formally:
\[
 d(t,s) = 
  \begin{cases} 
   |\textsl{size}(t)-\textsl{size}(s)| &\text {if } s \text{ and } t \text{ are}\\
                                       &\text{right-chain-homologous}\\
   \infty & \text {otherwise}\\
  \end{cases}
\] 
$e(t,s)$ would be the copy-number difference between the trees assuming that $t$ and $s$ aren't right-chain homologous, but are homologous. It would be $\infty$ if $t$ and $s$ are incompatible, and would be $0$ if both $t$ and $s$ are leaves and are equal. Otherwise, it would equal to the sum of $w(t_{1},s_{1})$ and $w(t_{2},s_{2})$.
\[
 e(t,s) = 
  \begin{cases} 
   0 &\text {if } t \text{ and } s \\
           &\text{are leaves and }\\
           &l(t)=l(s) \\
   \infty &\text {if } t \text{ and } s \\
           &\text{are incompatible }\\
   w(t_{1},s_{1})+w(t_{2},s_{2})&\text { otherwise}\\
  \end{cases}
\]
Finally we define $w(t,s)$ to be:
\begin{equation*}
    w(t,s)=\min(e(t,s),d(t,s))
\end{equation*}
}
\subsection{Equivalence query implementation}\label{supp::randomSEQ}
PCFGLearner supports three types of equivalence queries: Exhaustive Search, Random Sampling and Duplications Generator. In all these implementations, the oracle generates a set of trees $T$. Then, the oracle looks for a tree $t\in T$ s.t. $\mathcal{A}(t)\neq\query{smq}(t)$. If such a tree is found, it is returned as a counterexample, otherwise, a positive answer to the equivalence query is returned. The three implementations differ  in the way  they generate the trees.

In the Exhaustive Search equivalence query, given an alphabet $\Sigma$, and a maximum length $l$, all strings up to length $l$ are generated. For each string $s$, the optimal tree for it $t$ is constructed, as described in Section \ref{supp:trees}.

In the Random Sampling equivalence query, instead of generating all strings up-to length $l$,  two parameters are given, $r$ and $s$. For each $\query{seq}$, $r$ strings are independently sampled from a uniform distribution of all strings of length at most $s$. To each string the oracle then constructs the optimal tree, as in the Exhaustive Search equivalence query.

In the Duplications Generator, given a set of trees $R$, and a parameter $d$.  The oracle generates for each $t\in R$ all the trees $t'$ that can be obtained from $t$ by duplicating each of its leaves at most $d$ times. 

\subsection{Biological interpretation of the Multi Drug Resistance Efflux Pump grammar}\label{supp:biogramm}


In this section, we propose some biological interpretation of the grammar learned in the first example given in Section \ref{sec:demonstration} of the main paper, associating the highly probable rules of this grammar with explanatory evolutionary events, or with the functional reasoning underlying the strong conservation of the corresponding gene orders.  

AcrAB–TolC is a multidrug efflux pump that is widely distributed among gram-negative bacteria and extrudes diverse substrates from the cell, conferring resistance to a broad spectrum of antibiotics \cite{kobylka2020acrb}. This pump belongs to the resistance-nodulation-cell division (RND) family. In Gram-negative bacteria, RND pumps exist in a tripartite form, composed of an outer-membrane protein (TolC in our example), an inner membrane protein (AcrB in our example), and a periplasmic membrane fusion protein (AcrA in our example) that connects the other two proteins. The genes of the RND pump are often flanked with genes that code for local regulatory proteins, such as, in our example, the response regulator AcrR. 






 The pair of genes encoding the AcrB and AcrA proteins usually appear as an adjacent pair in our data, with AcrA preceding AcrB in the direction of transcription. The conserved order AcrA-AcrB could be explained by the order of assembly of the products of these genes into the AcrAB complex \cite{shi2019situ}, and by stochiometry  \cite{lalanne2018evolutionary}. The grammar learned for the AcrABR-TolC gene cluster (Figure \ref{fig:grammar1} in the main paper) indeed reflects this structural phenomenon, as $AB$, which is derived from the non-terminal $N_{2}$, is $4$ times more likely to be derived than $BA$, which is derived from the non-terminal $N_{4}$.



The outer-membrane protein TolC consistently appears, in our training dataset, adjacently to the AcrA-AcrB gene pair. However it forms a separate sub-tree from AcrAB in the highly probable trees generated by the learned grammar. This is due to the fact that, while the ordered pair AcrA-AcrB is very highly conserved in our data ($w(\text{AcrA }\text{AcrB})=31816.63$), TolC typically joins this triplet either upstream ($w(\text{TolC }\text{AcrA})=9494.15$) to it or downstream ($w(\text{AcrB }\text{TolC})=15783.51$) to it.

 Indeed, several studies indicate that the assembly and docking of the AcrAB-TolC efflux pump occur as a multi-step process, starting with the assembly of the AcrA-AcrB complex (see Figure \ref{fig:pump}), and only then activating the pump by the docking of TolC to the AcrAB complex \cite{ge2009c,shi2019situ}. 
 
 This assembly process is explained by additional studies, speculating that the TolC channel and inner membrane efflux AcrA-AcrB components may form a transient complex with the outer membrane channel TolC during efflux, due to the fact that TolC should be ready to use for not only AcrAB but also other efflux, secretion and transport systems in which it participates \cite{hayashi2016acrb}.
Indeed, in our general dataset, TolC participates in additional gene clusters encoding other export systems. This, along with the fact that in our string dataset this gene appears both upstream and downstream to the AcrAB pair, support the hypothesis that during the evolution of this pump across a wide-range of gram-negative bacteria, TolC was merged more than once with AcrAB (as well as with other export systems), in distinct evolutionary events. 


The gene cluster includes another gene, AcrR, that codes for a protein regulating the expression of the tripartite pump. This gene appears in a separate subtree from the AcrAB-TolC sub-tree, furthermore it is more likely to appear upstream to the AcrAB-TolC sub-tree in the highly probable trees.
 This could be explained by AcrR's functional annotation as a response regulator, whose role is to respond to the presence of a substrate, and consequently to enhance the expression of the RND tripartite efflux pump genes \cite{alvarez2013rnd}. 

 The fact that AcrR forms a separate subtree from the tripartite pump further exemplifies the role of merge events in gene cluster evolution. Indeed, other gene clusters in our dataset that include the tripartite pump are flanked by alternative response regulators, indicating that AcrAB-TolC homologs have merged with various regulators throughout the evoulution of gram-negative bacteria, yielding response to a variety of distinct drugs \cite{weston2018regulation}.
 
 Thus, the grammar learned by PCFGLearner exemplifies how our proposed approach can be harnessed to study biological systems that are conserved as gene clusters, and to explore
their function and their evolution.
\begin{figure}
   
    \scalebox{0.35}{\includegraphics{pump.png}}
    \caption{In vivo assembly and functioning mechanism for multidrug efflux pump AcrAB-TolC according to  \cite{ge2009c,shi2019situ}. First AcrB associates with AcrA, to form the bipartite complex AcrAB. Next, AcrA changes its conformation to recruit TolC. Once TolC binds with the AcrAB bipartite complex, the fully  assembled tripartite pump remains in the resting state. When AcrB encounters a drug molecule, the pump adopts conformation accompanied with a contraction along the long axis and the substrate is expelled through the channel and out of the cell. This figure was prepared according to Figure 4 in \cite{shi2019situ}. OM, outer membrane; PG, peptidoglycan; IM, inner membrane.}
    \vspace{-4mm}
    \label{fig:pump}
\end{figure}
\subsection{A grammar exemplifying duplication events}\label{supp:bioFimACD}
In this example, we applied PCFGLearner to the FimACD gene cluster data-set, using the duplication-event-counting edit-distance metric with decay factor $q=0.2$, and the Duplications Generator equivalence query with parameter $d=2$.

In the rest of this section we give a few selected rules from the resulting grammar, mainly to demonstrate that this grammar can generate an infinite number of strings, with exponentially decaying probabilities. The entire grammar is available in section \ref{sec:fimacd_grammar}.
The exemplified grammar allows each symbol in $\Sigma$ to duplicate with a probability of $0.2$ for each duplication. For example, for FimA we have:
\begin{align*}
    N_{7}&\rightarrow N_{1} N_{8} [0.8]\\
    N_{7}&\rightarrow N_{1} N_{7} [0.2]\\
    N_{8}&\rightarrow N_{1} N_{1} [1.0]\\
    N_{1}&\rightarrow FimA [1.0]
\end{align*}
We refer the reader to Figures~\ref{fig:fimACD_tree} and \ref{fig:fimA_dup}, for an example of a parse tree from the grammar, and an illustration of how the right-chain with $n$ FimA-tagged leaves can be obtained with probability of $0.8\cdot (0.2)^{n-3}$ for $n\geq 3$ from $N_{7}$. The term $n\geq 3$ is due to the fact that $N_{7}$ already represents a sub-tree learned from the data-set, with three consecutive copies of FimA.
\clearpage
\commentout
{For a duplication of FimC, we can derive $N_{10}\rightarrow N_{28} N_{29} [0.146]$, instead of $N_{10}\rightarrow N_{28} N_{3} [0.586]$. Note that this derivation is $4$ times less likely in our grammar. For further duplications of FimC, one can proceed with $N_{29}\rightarrow N_{3} N_{29} [0.2]$. The derivation of the sub-tree is completed, when the rule $N_{29}\rightarrow N_{3} N_{3} [0.8]$ is used (see figure \ref{fig:fimC_dup}).

Since a sequence of three FimA's appears in the data-set, one can notice that the probability of deriving three sequential FimA's is much larger than that of deriving three consecutive copies of other genes, that didn't appear consecutively in the data. 
For three FimA's, we need the derivations:
\begin{equation*}
    N_{7}\Rightarrow N_{1} N_{8}\Rightarrow FimA N_{1} N_{1}\Rightarrow FimA FimA FimA
\end{equation*}
whose product yields a total probability of $0.8$.

For deriving three FimC's we need to first derive $N_{10}\Rightarrow N_{28} N_{29}$ and then:
\begin{equation*}
    N_{29}\Rightarrow N_{3} N_{29}\Rightarrow FimC N_{3} N_{3}\Rightarrow FimC FimC FimC
\end{equation*}
The probability of deriving FimC FimC FimC from $N_{29}$ is $0.16$. Deriving $N_{29}$ from $N_{10}$ instead of $N_{3}$ is also $4$ times less likely, thus the probability for these two duplications is indeed $0.2\cdot0.2=0.04$.
}
\begin{figure} 
   
    \scalebox{0.25}{\includegraphics{tree4.png}}
    \caption{A parse tree from the grammar learned from the FimACD gene cluster  dataset. The marked sub-tree can grow indefinitely (see Figure~\ref{fig:fimA_dup}), using the production $N7\rightarrow N1 N7$ with a probability of $0.2$.}
    \vspace{-4mm}
    \label{fig:fimACD_tree}
\end{figure}

\begin{figure}
   
    \scalebox{0.4}{\includegraphics{tree_fimc2.png}}
    \caption{A right chain formed from $N7$, generating $n$ FimA's with a probability of $0.8\cdot (0.2)^{n-3}$ for $n\geq 3$}
    \vspace{-4mm}
    \label{fig:fimA_dup}
\end{figure}
\commentout{
\begin{figure}
   
    \scalebox{0.4}{\includegraphics{tree_fimc4.png}}
    \caption{The tree from figure \ref{fig:fimACD_tree}, with two duplications of the COG FimC}
    \vspace{-4mm}
    \label{fig:fimC_dup}
\end{figure}
}
\subsection{FimACD Grammar}\label{sec:fimacd_grammar}
\begin{tabular}{|c | c|}
Production & Probability\\
\hline
$S \rightarrow  N2 $&0.103\\
\hline
$S \rightarrow  N9 $&0.335\\
\hline
$S \rightarrow  N10 $&0.050\\
\hline
$S \rightarrow  N11 $&0.062\\
\hline
$S \rightarrow  N12 $&0.028\\
\hline
$S \rightarrow  N18 $&0.036\\
\hline
$S \rightarrow  N19 $&0.056\\
\hline
$S \rightarrow  N20 $&0.032\\
\hline
$S \rightarrow  N21 $&0.030\\
\hline
$S \rightarrow  N22 $&0.053\\
\hline
$S \rightarrow  N23 $&0.039\\
\hline
$S \rightarrow  N24 $&0.026\\
\hline
$S \rightarrow  N25 $&0.037\\
\hline
$S \rightarrow  N26 $&0.008\\
\hline
$S \rightarrow  N27 $&0.037\\
\hline
$S \rightarrow  N28 $&0.038\\
\hline
$S \rightarrow  N29 $&0.030\\
\hline
$N1 \rightarrow  \text{FimA} $&1.000\\
\hline
$N2 \rightarrow  N3\,N4 $&0.213\\
\hline
$N2 \rightarrow  N3\, N17 $&0.587\\
\hline
$N2 \rightarrow  N13\, N4 $&0.053\\
\hline
$N2 \rightarrow  N13\, N17 $&0.147\\
\hline
$N3 \rightarrow  \text{FimC} $&1.000\\
\hline
$N4 \rightarrow  \text{FimD} $&1.000\\
\hline
$N5 \rightarrow  \text{CitB} $&1.000\\
\hline
$N6 \rightarrow  N1\,N3 $&0.014\\
\hline
$N6 \rightarrow  N1\, N13 $&0.004\\
\hline
$N6 \rightarrow  N7\, N3 $&0.446\\
\hline
$N6 \rightarrow  N7\, N13 $&0.111\\
\hline
$N6 \rightarrow  N8\, N3 $&0.071\\
\hline
$N6 \rightarrow  N8\, N13 $&0.018\\
\hline
$N6 \rightarrow  N14\, N3 $&0.139\\
\hline
$N6 \rightarrow  N14\, N13 $&0.035\\
\hline
$N6 \rightarrow  N15\, N3 $&0.018\\
\hline
$N6 \rightarrow  N15\, N13 $&0.004\\
\hline
$N6 \rightarrow  N16\, N3 $&0.111\\
\hline
$N6 \rightarrow  N16\, N13 $&0.028\\
\hline
$N7 \rightarrow  N1\, N7 $&0.200\\
\hline
$N7 \rightarrow  N1\, N8 $&0.800\\
\hline
$N8 \rightarrow  N1\, N1 $&1.000\\
\hline
$N9 \rightarrow  N1\, N10 $&0.115\\
\hline
$N9 \rightarrow  N1\, N26 $&0.023\\
\hline
$N9 \rightarrow  N1\, N27 $&0.088\\
\hline
$N9 \rightarrow  N1\, N28 $&0.100\\
\hline
$N9 \rightarrow  N1\, N29 $&0.075\\
\hline
$N9 \rightarrow  N2\, N6 $&0.092\\
\hline
$N9 \rightarrow  N7\, N10 $&0.008\\
\hline
$N9 \rightarrow  N7\, N26 $&0.001\\
\hline
$N9 \rightarrow  N7\, N27 $&0.004\\
\hline
$N9 \rightarrow  N7\, N28 $&0.005\\
\hline
$N9 \rightarrow  N7\, N29 $&0.004\\
\hline
$N9 \rightarrow  N8\, N10 $&0.030\\
\hline
$N9 \rightarrow  N8\, N26 $&0.005\\
\hline
$N9 \rightarrow  N8\, N27 $&0.018\\
\hline
$N9 \rightarrow  N8\, N28 $&0.020\\
\hline
\end{tabular}
\newpage
\begin{tabular}{|c | c|}
$N9 \rightarrow  N8\, N29 $&0.015\\
\hline
$N9 \rightarrow  N11\, N6 $&0.085\\
\hline
$N9 \rightarrow  N12\, N6 $&0.021\\
\hline
$N9 \rightarrow  N15\, N2 $&0.016\\
\hline
$N9 \rightarrow  N15\, N10 $&0.008\\
\hline
$N9 \rightarrow  N15\, N19 $&0.016\\
\hline
$N9 \rightarrow  N15\, N20 $&0.004\\
\hline
$N9 \rightarrow  N15\, N25 $&0.018\\
\hline
$N9 \rightarrow  N16\, N2 $&0.004\\
\hline
$N9 \rightarrow  N16\, N10 $&0.002\\
\hline
$N9 \rightarrow  N16\, N19 $&0.004\\
\hline
$N9 \rightarrow  N16\, N20 $&0.001\\
\hline
$N9 \rightarrow  N16\, N25 $&0.004\\
\hline
$N9 \rightarrow  N18\, N5 $&0.053\\
\hline
$N9 \rightarrow  N18\, N30 $&0.013\\
\hline
$N9 \rightarrow  N19\, N5 $&0.009\\
\hline
$N9 \rightarrow  N19\, N30 $&0.002\\
\hline
$N9 \rightarrow  N20\, N5 $&0.014\\
\hline
$N9 \rightarrow  N20\, N30 $&0.003\\
\hline
$N9 \rightarrow  N21\, N5 $&0.013\\
\hline
$N9 \rightarrow  N21\, N30 $&0.003\\
\hline
$N9 \rightarrow  N22\, N5 $&0.009\\
\hline
$N9 \rightarrow  N22\, N30 $&0.002\\
\hline
$N9 \rightarrow  N23\, N5 $&0.017\\
\hline
$N9 \rightarrow  N23\, N30 $&0.004\\
\hline
$N9 \rightarrow  N24\, N5 $&0.002\\
\hline
$N9 \rightarrow  N24\, N30 $&0.001\\
\hline
$N9 \rightarrow  N25\, N5 $&0.055\\
\hline
$N9 \rightarrow  N25\, N30 $&0.014\\
\hline
$N10 \rightarrow  N4\, N3 $&0.213\\
\hline
$N10 \rightarrow  N4\, N13 $&0.053\\
\hline
$N10 \rightarrow  N17\, N3 $&0.587\\
\hline
$N10 \rightarrow  N17\, N13 $&0.147\\
\hline
$N11 \rightarrow  N1\, N2 $&1.000\\
\hline
$N12 \rightarrow  N7\, N2 $&0.200\\
\hline
$N12 \rightarrow  N8\, N2 $&0.800\\
\hline
$N13 \rightarrow  N3\, N3 $&0.800\\
\hline
$N13 \rightarrow  N3\, N13 $&0.200\\
\hline
$N14 \rightarrow  N1\, N15 $&0.640\\
\hline
$N14 \rightarrow  N1\, N16 $&0.160\\
\hline
$N14 \rightarrow  N7\, N15 $&0.032\\
\hline
$N14 \rightarrow  N7\, N16 $&0.008\\
\hline
$N14 \rightarrow  N8\, N15 $&0.128\\
\hline
$N14 \rightarrow  N8\, N16 $&0.032\\
\hline
$N15 \rightarrow  N7\, N1 $&0.200\\
\hline
$N15 \rightarrow  N8\, N1 $&0.800\\
\hline
$N16 \rightarrow  N7\, N7 $&0.040\\
\hline
$N16 \rightarrow  N7\, N8 $&0.160\\
\hline
$N16 \rightarrow  N8\, N7 $&0.160\\
\hline
$N16 \rightarrow  N8\, N8 $&0.640\\
\hline
$N17 \rightarrow  N4\, N1 $&0.003\\
\hline
$N17 \rightarrow  N4\, N4 $&0.073\\
\hline
$N17 \rightarrow  N4\, N7 $&0.108\\
\hline
$N17 \rightarrow  N4\, N8 $&0.017\\
\hline
$N17 \rightarrow  N4\, N14 $&0.034\\
\hline
\end{tabular}
\newpage
\begin{tabular}{|c | c|}
$N17 \rightarrow  N4\, N15 $&0.004\\
\hline
$N17 \rightarrow  N4\, N16 $&0.027\\
\hline
$N17 \rightarrow  N4\, N17 $&0.200\\
\hline
$N17 \rightarrow  N17\, N1 $&0.010\\
\hline
$N17 \rightarrow  N17\, N7 $&0.297\\
\hline
$N17 \rightarrow  N17\, N8 $&0.048\\
\hline
$N17 \rightarrow  N17\, N14 $&0.093\\
\hline
$N17 \rightarrow  N17\, N15 $&0.012\\
\hline
$N17 \rightarrow  N17\, N16 $&0.074\\
\hline
$N18 \rightarrow  N1\, N25 $&1.000\\
\hline
$N19 \rightarrow  N2\, N1 $&1.000\\
\hline
$N20 \rightarrow  N2\, N7 $&0.800\\
\hline
$N20 \rightarrow  N2\, N16 $&0.200\\
\hline
$N21 \rightarrow  N7\, N25 $&0.200\\
\hline
$N21 \rightarrow  N8\, N25 $&0.800\\
\hline
$N22 \rightarrow  N1\, N19 $&1.000\\
\hline
$N23 \rightarrow  N1\, N20 $&0.800\\
\hline
$N23 \rightarrow  N7\, N20 $&0.040\\
\hline
$N23 \rightarrow  N8\, N20 $&0.160\\
\hline
$N24 \rightarrow  N7\, N19 $&0.200\\
\hline
$N24 \rightarrow  N8\, N19 $&0.800\\
\hline
$N25 \rightarrow  N2\, N8 $&0.800\\
\hline
$N25 \rightarrow  N2\, N15 $&0.200\\
\hline
$N26 \rightarrow  N2\, N14 $&1.000\\
\hline
$N27 \rightarrow  N10\, N1 $&1.000\\
\hline
$N28 \rightarrow  N10\, N7 $&0.640\\
\hline
$N28 \rightarrow  N10\, N14 $&0.200\\
\hline
$N28 \rightarrow  N10\, N16 $&0.160\\
\hline
$N29 \rightarrow  N10\, N8 $&0.800\\
\hline
$N29 \rightarrow  N10\, N15 $&0.200\\
\hline
$N30 \rightarrow  N5\, N5 $&0.800\\
\hline
$N30 \rightarrow  N5\, N30 $&0.200\\
\hline
\end{tabular}
\newpage


\stepcounter{section}
\section{new}
\startprod{S} \makebox[10cm]{\derivation{R N7}{0.456}{45}\derivation{R N3}{0.185}{18}\derivation{C N1}{0.137}{13}\derivation{N7 R}{0.078}{7}}

\makebox[10.55cm]{\derivation{R N6}{0.053}{5}\derivation{N1 C}{0.034}{3}\derivation{N5 R}{0.028}{2}\derivation{N6 R}{0.013}{1}}

\makebox[6.2cm]{\derivation{N3 R}{0.012}{1}\lastderivation{R N5}{0.004}{0}}

\startprod{N1} \derivation{R N2}{0.640}{64}\derivation{N2 R}{0.160}{16}\derivation{R N4}{0.160}{16}\lastderivation{N4 R}{0.040}{4}

\startprod{N2} \lastderivation{A B}{1.000}{100} \startprod{N3} \lastderivation{C N2}{1.000}{100}  \startprod{N4} \lastderivation{B A}{1.000}{100}

\startprod{N5} \lastderivation{N4 C}{1.000}{100} \startprod{N6} \derivation{C N4}{0.882}{88}\derivation{N8 A}{0.095}{9}\lastderivation{A N8}{0.024}{2}

\startprod{N7} \lastderivation{N2 C}{1.000}{100} \startprod{N8} \derivation{B C}{0.800}{80}\lastderivation{C B}{0.200}{20}

\startprod{R} \lastderivation{AcrR}{1.000}{100} \startprod{A} \lastderivation{AcrA}{1.000}{100} \startprod{B} \lastderivation{AcrB}{1.000}{100} 
\startprod{C} \lastderivation{TolC}{1.000}{100}

\begin{figure}
    \centering
    \caption{The most probable tree in the grammar, with $p=0.456$}
    \label{fig:tree1}
    \scalebox{1}{
\begin{tikzpicture}
\tikzstyle{myarrow}=[line width=3mm,draw=#1]
\draw [myarrow={cyan}](1.2,3.5)--(-0,3.5);
\draw [myarrow={red}](1.4,3.5)--(2.6,3.5);
\draw [myarrow={green}](3,3.5)--(4.2,3.5); 
\draw [myarrow={yellow}](4.5,3.5)--(5.7,3.5); 
\node[draw=none] (S) at (2.5, 6) {$S$};
\node[draw=none] (R) at (0.6, 5) {$R$};
\node[draw=none] (A) at (2, 4.25) {$A$};
\node[draw=none] (B) at (3.5, 4.25) {$B$};
\node[draw=none] (C) at (5, 4.25) {$C$};
\node[draw=none] (N2) at (2.7, 5) {$N_{2}$};
\node[draw=none] (N7) at (3.7, 5.5) {$N_{7}$};
\node[draw=none] (acrA) at (2,3.5) {AcrA};
\node[draw=none] (acrB) at (3.5,3.5) {AcrB};
\node[draw=none] (tolC) at (5,3.5) {TolC};
\node[draw=none] (acrR) at (0.6,3.5) {AcrR};
\draw (S) -- (N7);
\draw (S) -- (R);
\draw (N7) -- (N2);
\draw (N7) -- (C);
\draw (N2) -- (A);
\draw (N2) -- (B);
\draw (R) -- (acrR);
\draw (A) -- (acrA);
\draw (B) -- (acrB);
\draw (C) -- (tolC);
\end{tikzpicture}}
\end{figure}
\begin{figure}
    \centering
    \caption{The least probable tree in the grammar, with $p=0.001$}
    \label{fig:tree2}
\begin{tikzpicture}
\tikzstyle{myarrow}=[line width=3mm,draw=#1]
\draw [myarrow={cyan}](3,3.75)--(4.2,3.75); 
\draw [myarrow={red}](1.4,3.75)--(2.6,3.75);
\draw [myarrow={green}](1.2,3.75)--(-0,3.75);
\draw [myarrow={yellow}](4.5,3.75)--(5.7,3.75); 
\node[draw=none] (S) at (3.5, 6) {$S$};
\node[draw=none] (N1) at (2.5, 5.75) {$N_{1}$};
\node[draw=none] (A) at (2, 4.5) {$A$};
\node[draw=none] (B) at (0.5, 4.5) {$B$};
\node[draw=none] (R) at (3.5, 5) {$R$};
\node[draw=none] (N4) at (1.25, 5) {$N_{4}$};
\node[draw=none] (C) at (5, 5) {$C$};
\node[draw=none] (acrA) at (2,3.75) {AcrA};
\node[draw=none] (acrB) at (0.5,3.75) {AcrB};
\node[draw=none] (tolC) at (5,3.75) {TolC};
\node[draw=none] (acrR) at (3.5,3.75) {AcrR};

\draw (S) -- (N1);
\draw (S) -- (C);
\draw (N1) -- (N4);
\draw (N1) -- (R);
\draw (N4) -- (B);
\draw (N4) -- (A);
\draw (R) -- (acrR);
\draw (A) -- (acrA);
\draw (B) -- (acrB);
\draw (C) -- (tolC);
\end{tikzpicture}
\end{figure}

\begin{figure}
    \centering
    \caption{The PQ-tree for the AcrABR-TolC dataset}
    \label{fig:tree3}
\begin{tikzpicture}
\tikzstyle{myarrow}=[line width=3mm,draw=#1]
\draw [myarrow={cyan}](1,2)--(3,2);
\draw [myarrow={red}](0.8,2)--(-1.2,2);
\draw [myarrow={green}](3.2,2)--(5,2);
\draw [myarrow={yellow}](5.2,2)--(7,2); 
\node[shape=circle,draw=black] (P) at (3, 3) {};
\node[draw=none] (acrA) at (0,2) {AcrA};
\node[draw=none] (acrB) at (3.7,2) {AcrB};
\node[draw=none] (tolC) at (5.7,2) {TolC};
\node[draw=none] (acrR) at (1.7,2) {AcrR};

\draw (P) -- (acrR);
\draw (P) -- (acrA);
\draw (P) -- (acrB);
\draw (P) -- (tolC);
\end{tikzpicture}
\end{figure}


\tikzset{
	label/.style={
		rectangle,
		draw=white,
		text centered,
	},
}

\begin{figure}
	\centering
	\caption{The PQ-tree for the AcrABR-TolC dataset}
	\label{fig:tree3b}
	\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=1.5cm,initial text=, initial where=above]	

\node[shape=circle,draw=black] (R)  { };			

\node[label] (M) [below of=R, node distance=2.0cm] {};
\node[label] (M2) [left of=M, node distance=0.5cm, rotate=90,fill=green] {AcrB};
\node[label] (M1) [left of=M, node distance=1.5cm, rotate=90,fill=red] {AcrA};
\node[label] (M3) [right of=M, node distance=0.5cm, rotate=90,fill=yellow] {TolC};
\node[label] (M4) [right of=M, node distance=1.5cm, rotate=90,fill=cyan] {AcrR};

\path (R) edge [-]  node  { } (M1);
\path (R) edge [-]  node  { } (M2);
\path (R) edge [-]  node  { } (M3);
\path (R) edge [-]  node  { } (M4);

	\end{tikzpicture}
\end{figure}

\vspace{2mm}

\begin{figure}
	\centering

	\label{fig:tree1}
	\scalebox{1}{
		\begin{tikzpicture}
		\tikzstyle{myarrow}=[line width=3mm,draw=#1]
	
	
	
	
		\node[draw=none] (S) at (2.5, 6) {$S$};
		\node[draw=none] (R) at (0.6, 5) {$R$};
		\node[draw=none] (A) at (2, 4.25) {$A$};
		\node[draw=none] (B) at (3.5, 4.25) {$B$};
		\node[draw=none] (C) at (5, 4.25) {$C$};
		\node[draw=none] (N2) at (2.7, 5) {$N_{2}$};
		\node[draw=none] (N7) at (3.7, 5.5) {$N_{7}$};
		\node[draw=none, fill=red] (acrA) at (2,3.5) {AcrA};
		\node[draw=none,fill=green] (acrB) at (3.5,3.5) {AcrB};
		\node[draw=none,fill=yellow] (tolC) at (5,3.5) {TolC};
		\node[draw=none,fill=cyan] (acrR) at (0.6,3.5) {AcrR};
		\draw (S) -- (N7);
		\draw (S) -- (R);
		\draw (N7) -- (N2);
		\draw (N7) -- (C);
		\draw (N2) -- (A);
		\draw (N2) -- (B);
		\draw (R) -- (acrR);
		\draw (A) -- (acrA);
		\draw (B) -- (acrB);
		\draw (C) -- (tolC);
		
		\node[label] (H) [right of=S, node distance=4.8cm]   {};			
		
		\node[shape=circle,draw=black, above of=H, node distance=0.7cm] (RR)  { };			
		
		\node[label] (M) [below of=RR, node distance=2.0cm] {};
		\node[label] (M2) [left of=M, node distance=0.5cm, rotate=90,fill=green] {AcrB};
		\node[label] (M1) [left of=M, node distance=1.5cm, rotate=90,fill=red] {AcrA};
		\node[label] (M3) [right of=M, node distance=0.5cm, rotate=90,fill=yellow] {TolC};
		\node[label] (M4) [right of=M, node distance=1.5cm, rotate=90,fill=cyan] {AcrR};
		
		\path (RR) edge [-]  node  { } (M1);
		\path (RR) edge [-]  node  { } (M2);
		\path (RR) edge [-]  node  { } (M3);
		\path (RR) edge [-]  node  { } (M4);
		
	
	
	
	
		\node[draw=none] (SS) at (12.5, 6) {$S$};
		\node[draw=none] (SN1) at (11.3, 5.45) {$N_{1}$};
		\node[draw=none] (SA) at (11, 4.25) {$A$};
		\node[draw=none] (SB) at (9.5, 4.25) {$B$};
		\node[draw=none] (SR) at (12.5, 5) {$R$};
		\node[draw=none] (SN4) at (10.25, 5) {$N_{4}$};
		\node[draw=none] (SC) at (14, 5) {$C$};
		\node[draw=none, fill=red] (SacrA) at (11,3.5) {AcrA};
		\node[draw=none,fill=green] (SacrB) at (9.5,3.5) {AcrB}; %
		\node[draw=none,fill=yellow] (StolC) at (14,3.5) {TolC}; %
		\node[draw=none,fill=cyan] (SacrR) at (12.5,3.5) {AcrR};		
		
		\draw (SS) -- (SN1);
		\draw (SS) -- (SC);
		\draw (SN1) -- (SN4);
		\draw (SN1) -- (SR);
		\draw (SN4) -- (SB);
		\draw (SN4) -- (SA);
		\draw (SR) -- (SacrR);
		\draw (SA) -- (SacrA);
		\draw (SB) -- (SacrB);
		\draw (SC) -- (StolC);
		
		
		
		\end{tikzpicture}}
\end{figure}


\section{basic}

\startprod{S} \makebox[10.3cm]{\derivation{$R$ $N_{6}$}{0.522}{52}\derivation{$R$ $N_{3} $}{0.194}{19}\derivation{$N_{6}$ $N_{1}$}{0.132}{13}\derivation{$N_{6}$ $R$}{0.089}{8}}

\makebox[10.65cm]{\derivation{$N_{1}$ $N_{6}$}{0.026}{2}\derivation{$N_{7}$ $R$}{0.020}{2}\derivation{$N_{3}$ $R$}{0.013}{1}\lastderivation{$R$ $N_{7}$}{0.004}{0}}

\startprod{N_{1}} \derivation{$R$ $N_{2}$}{0.694}{69}\derivation{$N_{2}$ $R$}{0.139}{13}\derivation{$R$ $N_{4}$}{0.139}{13}\lastderivation{$N_{4}$ $R$}{0.028}{2}

\startprod{N_{2}} \lastderivation{$A$ $B$}{1.000}{100}, \startprod{N_{3}} \lastderivation{$C$ $N_{2}$}{1.000}{100}, \startprod{N_{4}} \lastderivation{$B$ $A$}{1.000}{100}

\startprod{N_{5}} \derivation{$B$ $C$}{0.833}{83}\lastderivation{$C$ $B$}{0.167}{16}

\startprod{N_{6}} \derivation{$N_{2}$ $C$}{0.915}{91}\derivation{$C$ $N_{4}$}{0.074}{7}\derivation{$N_{5}$ $A$}{0.010}{0}\lastderivation{$A$ $N_{5}$}{0.002}{0}

\startprod{N_{7}} \derivation{$N_{4}$ $C$}{0.933}{93}\derivation{$C$ $N_{4}$}{0.058}{5}\derivation{$N_{5}$ $A$}{0.008}{0}\lastderivation{$A$ $N_{5}$}{0.002}{0}

\startprod{R} \makebox[2.35cm]{\lastderivation{AcrR}{1.000}{100}},\startprod{A} \makebox[2.2cm]{\lastderivation{AcrA}{1.000}{100}}, \startprod{B} \makebox[2.2cm]{\lastderivation{AcrB}{1.000}{100}}, \startprod{C} \makebox[2.2cm]{\lastderivation{TolC}{1.000}{100}}

\section{all}
\startprod{S} \makebox[10cm]{\derivation{N1 N8}{0.326}{32}\derivation{N1 N6}{0.132}{13}\derivation{N4 N14}{0.090}{9}\derivation{N8 N1}{0.055}{5}}

\makebox[11.1cm]{\derivation{N10 N8}{0.046}{4}\derivation{N19 N8}{0.031}{3}\derivation{N11 N8}{0.028}{2}\derivation{N1 N12}{0.026}{2}}

\makebox[11.3cm]{\derivation{N13 N20}{0.023}{2}\derivation{N6 N20}{0.018}{1}\derivation{N14 N4}{0.018}{1}\derivation{N8 N10}{0.017}{1}}

\makebox[11.3cm]{\derivation{N20 N8}{0.016}{1}\derivation{N13 N19}{0.016}{1}\derivation{N19 N6}{0.014}{1}\derivation{N11 N6}{0.014}{1}}

\makebox[11.3cm]{\derivation{N13 N1}{0.013}{1}\derivation{N8 N11}{0.010}{0}\derivation{N10 N6}{0.009}{0}\derivation{N20 N13}{0.009}{0}}

\makebox[11.1cm]{\derivation{N6 N1}{0.009}{0}\derivation{N8 N19}{0.006}{0}\derivation{N20 N6}{0.006}{0}\derivation{N11 N13}{0.006}{0}}

\makebox[11.5cm]{\derivation{N10 N13}{0.006}{0}\derivation{N12 N1}{0.005}{0}\derivation{N12 N20}{0.005}{0}\derivation{N8 N20}{0.005}{0}}

\makebox[11.5cm]{\derivation{N20 N12}{0.004}{0}\derivation{N1 N16}{0.004}{0}\derivation{N6 N19}{0.004}{0}\derivation{N13 N10}{0.003}{0}}

\makebox[11.9cm]{\derivation{N12 N19}{0.003}{0}\derivation{N19 N13}{0.003}{0}\derivation{N19 N12}{0.003}{0}\derivation{N11 N12}{0.003}{0}}

\makebox[11.3cm]{\derivation{N6 N11}{0.003}{0}\derivation{N6 N10}{0.003}{0}\derivation{N1 N13}{0.003}{0}\derivation{N13 N11}{0.002}{0}}

\makebox[11.6cm]{\derivation{N10 N12}{0.002}{0}\derivation{N16 N1}{0.001}{0}\derivation{N12 N10}{0.001}{0}\derivation{N12 N11}{0.001}{0}}


\startprod{N18} \derivation{OmpR}{1.000}{100}

\startprod{N17} \derivation{BaeS}{1.000}{100}

\startprod{N3} \derivation{AcrB}{1.000}{100}

\startprod{N11} \derivation{MarR}{1.000}{100}

\startprod{N1} \derivation{AcrR}{1.000}{100}

\startprod{N10} \derivation{LysR}{1.000}{100}

\startprod{N4} \derivation{TolC}{1.000}{100}

\startprod{N2} \derivation{AcrA}{1.000}{100}


\startprod{N6} \derivation{N4 N5}{1.000}{100}

\startprod{N12} \derivation{N4 N9}{1.000}{100}



\startprod{N19} \derivation{N17 N18}{1.000}{100}

\startprod{N16} \derivation{N15 N2}{0.833}{83}\derivation{N2 N15}{0.167}{16}

\startprod{N13} \derivation{N9 N4}{1.000}{100}

\startprod{N8} \derivation{N5 N4}{1.000}{100}

\startprod{N5} \derivation{N2 N3}{1.000}{100}

\startprod{N20} \derivation{N18 N17}{1.000}{100}

\startprod{N14} \derivation{N1 N5}{0.694}{69}\derivation{N5 N1}{0.139}{13}\derivation{N1 N9}{0.139}{13}\derivation{N9 N1}{0.028}{2}

\startprod{N15} \derivation{N3 N4}{0.833}{83}\derivation{N4 N3}{0.167}{16}

\startprod{N9} \derivation{N3 N2}{1.000}{100}




\section{LysR and MarR}
\startprod{S}\makebox[10cm]{\derivation{R N8}{0.39}{80}\derivation{R N6}{0.16}{40}\derivation{C N14}{0.11}{40}\derivation{N8 R}{0.06}{20}\derivation{L N8}{0.05}{20}}

\makebox[8.8cm]{\derivation{M N8}{0.03}{10}\derivation{R N12}{0.03}{10}\derivation{N14 C}{0.02}{10}
\derivation{L N8}{0.05}{20}}

\makebox[9cm]{\derivation{N8 L}{0.02}{10}\derivation{M N6}{0.017}{0}\derivation{N13 R}{0.015}{0}
\derivation{N8 M}{0.01}{0}}

\makebox[11.3cm]{\derivation{L N6}{0.01}{0}\derivation{N6 R}{0.01}{0}
\derivation{L N13}{0.006}{0}\derivation{M N13}{0.006}{0}\derivation{N12 R}{0.006}{0}}

\makebox[9.8cm]{\derivation{R N16}{0.005}{0}\derivation{N13 L}{0.004}{0}\derivation{R N13}{0.003}{0}
\derivation{M N12}{0.003}{0}}

\makebox[9.5cm]{\derivation{N6 L}{0.003}{0}\derivation{N6 M}{0.003}{0}
\derivation{N13 M}{0.002}{0}\derivation{L N12}{0.002}{0}}

\makebox[8cm]{\derivation{N16 R}{0.0009}{0}\derivation{N12 L}{0.0008}{0}\derivation{N12 M}{0.0006}{0}}

\startprod{N5} \derivation{A B}{1.0}{100}

\startprod{N6} \derivation{C N5}{1.0}{100}

\startprod{N8}\derivation{N5 C}{1.0}{100}

\startprod{N9}\derivation{B A}{1.0}{100}

\startprod{N12}\derivation{C N9}{1.0}{100}

\startprod{N13}\derivation{N9 C}{1.0}{100}

\startprod{N14}\derivation{R N5}{0.69}{70}\derivation{R N9}{0.138}{20}\derivation{N5 R}{0.138}{20}\derivation{N9 R}{0.02}{10}

\startprod{N15}\derivation{B C}{0.83}{70}\derivation{C B}{0.17}{20}

\startprod{N16}\derivation{N15 A}{0.83}{70}\derivation{A N15}{0.17}{20}
\section{Only LysR}
\startprod{S} \makebox[8cm]{\derivation{R N9}{0.43}{100}\derivation{R N6}{0.20}{50}\derivation{C N12}{0.12}{50}\derivation{N9 R}{0.07}{25}}\\
\makebox[11cm]{\derivation{L N9}{0.06}{25}\derivation{N12 C}{0.023}{10}\derivation{N9 L}{0.022}{10} \derivation{N14 R}{0.017}{0}}\\
\makebox[11.3cm]{\derivation{L N6}{0.014}{0}\derivation{L N14}{0.007}{0}\derivation{R N11}{0.005}{0}\derivation{N14 L}{0.004}{0}}\\
\makebox[9.1cm]{
\derivation{N6 L}{0.004}{0}\derivation{R N14}{0.004}{0}\derivation{N11 R}{0.001}{0}}

\startprod{N5} \derivation{A B}{1.0}{100}

\startprod{N6}  \derivation{C N5}{0.85}{100}\derivation{C N13}{0.15}{50}

\startprod{N9}  \hlc[yellow]{N5 C [0.99]}$\mid$ C N13 [0.01]

\startprod{N10}  \hlc[yellow]{B C [0.83]} $\mid$ \hlc[yellow!50]{C B [0.17]}

\startprod{N11}  \hlc[yellow]{A N10 [0.83]} $\mid$ \hlc[yellow!50]{N10 A [0.17]}

\startprod{N12}  \hlc[yellow]{R N5 [0.69]}$\mid$ \hlc[yellow!50]{R N13 [0.14]} $\mid$ \hlc[yellow!50]{N5 R [0.14]}$\mid$ N13 R [0.01]

\startprod{N13}  \hlc[yellow]{B A [1.0]}

\startprod{N14}  \hlc[yellow]{N13 C [1.0]}

\startprod{R}  \hlc[yellow]{'AcrR' [1.0]}

\startprod{A} \hlc[yellow]{'AcrA' [1.0]}

\startprod{B}  \hlc[yellow]{'AcrB' [1.0]}

\startprod{C}  \hlc[yellow]{'TolC' [1.0]}

\startprod{L}  \hlc[yellow]{'LysR' [1.0]}

\section{Duplications}
\startprod{N8} \derivation{N3 N4}{1.000}{100}

\startprod{N3} \derivation{AcrB}{0.724}{72}\derivation{N3 N3}{0.276}{27}

\startprod{N12} \derivation{N10 N4}{0.500}{50}\derivation{N8 N2}{0.500}{50}

\startprod{N10} \derivation{N3 N2}{1.000}{100}

\startprod{N1} \derivation{AcrR}{0.724}{72}\derivation{N1 N1}{0.276}{27}

\startprod{N4} \derivation{TolC}{0.724}{72}\derivation{N4 N4}{0.276}{27}

\startprod{N2} \derivation{AcrA}{0.724}{72}\derivation{N2 N2}{0.276}{27}

\startprod{N6} \derivation{N4 N5}{1.000}{100}

\startprod{N11} \derivation{N5 N4}{1.000}{100}

\startprod{S} \derivation{N7}{1.000}{100}

\startprod{N5} \derivation{N2 N3}{1.000}{100}

\startprod{N9} \derivation{N1 N5}{1.000}{100}

\startprod{N7} \makebox[10cm]{\derivation{N1 N11}{0.552}{55}\derivation{N1 N6}{0.224}{22}\derivation{N4 N9}{0.106}{10}\derivation{N11 N1}{0.094}{9}}

\makebox[10cm]{\derivation{N6 N1}{0.014}{1}\derivation{N1 N12}{0.010}{0}}


\section{duplications 2}
\startprod{N8} \derivation{N1 N1}{1.000}{100}

\startprod{N5} \derivation{N1 N4}{0.800}{80}\derivation{N8 N4}{0.160}{16}\derivation{N9 N4}{0.040}{3}

\startprod{N2} \derivation{FimC}{1.000}{100}

\startprod{N19} \makebox[10cm]{\derivation{N1 N10}{0.715}{71}\derivation{N1 N14}{0.125}{12}\derivation{N8 N10}{0.103}{10}\derivation{N9 N10}{0.026}{2}}

\makebox[10cm]{\derivation{N8 N14}{0.025}{2}\derivation{N9 N14}{0.006}{0}}



\startprod{N20} \derivation{N2 N2}{0.800}{80}\derivation{N2 N20}{0.200}{19}

\startprod{N24} \makebox[10cm]{\derivation{N1 N16}{0.124}{12}\derivation{N1 N13}{0.099}{9}\derivation{N1 N6}{0.098}{9}\derivation{N5 N25}{0.091}{9}}

\makebox[10cm]{\derivation{N19 N21}{0.087}{8}\derivation{N4 N25}{0.079}{7}\derivation{N10 N21}{0.064}{6}\derivation{N22 N2}{0.054}{5}}

\makebox[10cm]{\derivation{N8 N6}{0.026}{2}\derivation{N8 N7}{0.026}{2}\derivation{N8 N16}{0.025}{2}\derivation{N8 N4}{0.024}{2}}

\makebox[10cm]{\derivation{N18 N21}{0.023}{2}\derivation{N1 N17}{0.020}{1}\derivation{N8 N13}{0.020}{1}\derivation{N14 N21}{0.016}{1}}

\makebox[10cm]{\derivation{N11 N10}{0.015}{1}\derivation{N11 N4}{0.014}{1}\derivation{N22 N20}{0.014}{1}\derivation{N11 N7}{0.013}{1}}

\makebox[10cm]{\derivation{N7 N21}{0.010}{1}\derivation{N11 N6}{0.006}{0}\derivation{N9 N6}{0.006}{0}\derivation{N9 N7}{0.006}{0}}

\makebox[10cm]{\derivation{N9 N16}{0.006}{0}\derivation{N9 N4}{0.006}{0}\derivation{N9 N13}{0.005}{0}\derivation{N8 N17}{0.004}{0}}

\makebox[10cm]{\derivation{N23 N10}{0.004}{0}\derivation{N11 N14}{0.004}{0}\derivation{N23 N4}{0.004}{0}\derivation{N23 N7}{0.003}{0}}

\makebox[10cm]{\derivation{N23 N6}{0.002}{0}\derivation{N9 N17}{0.001}{0}\derivation{N23 N14}{0.001}{0}\derivation{N9 N15}{0.000}{0}}

\makebox[10cm]{\derivation{N8 N15}{0.000}{0}\derivation{N1 N15}{0.000}{0}}



\startprod{N25} \makebox[10cm]{\derivation{N9 N2}{0.446}{44}\derivation{N12 N2}{0.139}{13}\derivation{N9 N20}{0.111}{11}\derivation{N23 N2}{0.111}{11}}

\makebox[10cm]{\derivation{N8 N2}{0.071}{7}\derivation{N12 N20}{0.035}{3}\derivation{N23 N20}{0.028}{2}\derivation{N8 N20}{0.018}{1}}

\makebox[10cm]{\derivation{N11 N2}{0.018}{1}\derivation{N1 N2}{0.014}{1}\derivation{N11 N20}{0.004}{0}\derivation{N1 N20}{0.004}{0}}



\startprod{N11} \derivation{N8 N1}{0.800}{80}\derivation{N9 N1}{0.200}{19}

\startprod{N4} \derivation{N2 N3}{0.800}{80}\derivation{N20 N3}{0.200}{19}

\startprod{N23} \derivation{N8 N8}{0.640}{64}\derivation{N9 N8}{0.160}{15}\derivation{N8 N9}{0.160}{15}\derivation{N9 N9}{0.040}{3}

\startprod{N12} \makebox[10cm]{\derivation{N1 N11}{0.640}{64}\derivation{N1 N23}{0.160}{15}\derivation{N8 N11}{0.128}{12}\derivation{N9 N11}{0.032}{3}}

\makebox[10cm]{\derivation{N8 N23}{0.032}{3}\derivation{N9 N23}{0.008}{0}}



\startprod{N18} \makebox[10cm]{\derivation{N1 N7}{0.439}{43}\derivation{N1 N14}{0.206}{20}\derivation{N8 N10}{0.155}{15}\derivation{N8 N7}{0.088}{8}}

\makebox[10cm]{\derivation{N8 N14}{0.041}{4}\derivation{N9 N10}{0.039}{3}\derivation{N9 N7}{0.022}{2}\derivation{N9 N14}{0.010}{1}}



\startprod{N22} \makebox[10cm]{\derivation{N3 N9}{0.557}{55}\derivation{N3 N12}{0.174}{17}\derivation{N3 N23}{0.139}{13}\derivation{N3 N8}{0.089}{8}}

\makebox[10cm]{\derivation{N3 N11}{0.022}{2}\derivation{N3 N1}{0.018}{1}}



\startprod{N6} \derivation{N3 N2}{0.800}{80}\derivation{N3 N20}{0.200}{19}

\startprod{N13} \derivation{N6 N1}{0.755}{75}\derivation{N6 N8}{0.196}{19}\derivation{N6 N11}{0.049}{4}

\startprod{N14} \derivation{N4 N9}{0.800}{80}\derivation{N4 N23}{0.200}{19}

\startprod{S} \makebox[10cm]{\derivation{N24}{0.380}{37}\derivation{N18}{0.117}{11}\derivation{N4}{0.100}{10}\derivation{N5}{0.075}{7}}

\makebox[10cm]{\derivation{N7}{0.054}{5}\derivation{N16}{0.054}{5}\derivation{N19}{0.049}{4}\derivation{N6}{0.048}{4}}

\makebox[10cm]{\derivation{N13}{0.047}{4}\derivation{N10}{0.036}{3}\derivation{N14}{0.031}{3}\derivation{N17}{0.008}{0}}

\makebox[10cm]{\derivation{N15}{0.000}{0}}



\startprod{N3} \derivation{FimD}{0.724}{72}\derivation{N3 N3}{0.276}{27}

\startprod{N7} \derivation{N4 N1}{1.000}{100}

\startprod{N1} \derivation{FimA}{1.000}{100}

\startprod{N9} \derivation{N1 N8}{0.800}{80}\derivation{N1 N9}{0.200}{19}

\startprod{N10} \derivation{N4 N8}{0.800}{80}\derivation{N4 N11}{0.200}{19}

\startprod{N17} \derivation{N4 N12}{1.000}{100}

\startprod{N21} \derivation{CitB}{0.724}{72}\derivation{N21 N21}{0.276}{27}

\startprod{N16} \makebox[10cm]{\derivation{N6 N9}{0.438}{43}\derivation{N6 N8}{0.253}{25}\derivation{N6 N12}{0.137}{13}\derivation{N6 N23}{0.109}{10}}

\makebox[10cm]{\derivation{N6 N11}{0.063}{6}}




\section{figures}
\begin{tikzpicture}
\tikzstyle{myarrow}=[line width=1.5mm,draw=#1,-triangle 45,postaction={draw, line width=4mm, shorten >=5mm, -}]
\draw [myarrow={cyan}](0.8,2)--(-1.2,2);
\draw [myarrow={red}](1,2)--(3,2);
\draw [myarrow={blue}](3.2,2)--(5,2); 
\draw [myarrow={yellow}](5.2,2)--(7,2); 
\node[draw=none] (S) at (2.5, 6) {$S$};
\node[draw=none] (N1) at (0, 4) {$R$};
\node[draw=none] (N2) at (1.7, 3) {$A$};
\node[draw=none] (N3) at (3.7, 3) {$B$};
\node[draw=none] (N4) at (5.7, 3) {$C$};
\node[draw=none] (N5) at (2.7, 4) {$N_{5}$};
\node[draw=none] (N9) at (3.7, 5) {$N_{9}$};
\node[draw=none] (A) at (1.7,2) {acrA};
\node[draw=none] (B) at (3.7,2) {acrB};
\node[draw=none] (C) at (5.7,2) {tolC};
\node[draw=none] (R) at (0,2) {acrR};
\draw (S) -- (N9);
\draw (N9) -- (N5);
\draw (N9) -- (N4);
\draw (N5) -- (N2);
\draw (N5) -- (N3);
\draw (S) -- (N1);
\draw (N1) -- (R);
\draw (N2) -- (A);
\draw (N3) -- (B);
\draw (N4) -- (C);
\end{tikzpicture}
\end{document}




\section{Introduction}\label{sec:intro}

Probabilistic context free grammars (PCFGs) constitute a computational model suitable for probabilistic systems which observe non-regular (yet context-free) behavior. They are vastly used in computational linguistics~\parciteauthor{Chomsky56}, natural language processing~\parciteauthor{church-1988-stochastic} and biological modeling, for instance, in probabilistic modeling of RNA structures~\parciteauthor{Grate95}.  Methods for learning PCFGs from experimental data have been thought for over half a century.
Unfortunately, there are various hardness results regarding learning context-free grammars in general and probabilistic grammars in particular. 
It follows from~\parciteauthor{Gold78}  that context-free grammars (CFGs) cannot be identified in the limit from positive examples, and from~\cite{Angluin90}  that CFGs cannot be identified in polynomial time using equivalence queries only. Both results are not surprising for those familiar with learning regular languages, as they hold for the class of regular languages as well. However, while regular languages can be learned using both membership queries and equivalence queries~\cite{Angluin87}, it was shown   that learning CFGs using both membership queries and equivalence queries  
is computationally as hard as key cryptographic problems for which there is currently no known polynomial-time algorithm~\parciteauthor{AngluinK95}. {See more on the difficulties of learning context-free grammars in~\cite[Chapter 15]{delaHiguera}.}
Hardness results for the probabilistic setting have also been established. \parciteauthor{AbeW92} have shown a computational hardness result for the inference of probabilistic automata, in particular, that an exponential blowup with respect to the alphabet size is inevitable unless $\complexityclass{RP} = \complexityclass{NP}$. 

The problem of identifying a probabilistic grammar from examples has two aspects: the first is determining the rules of the grammar up to variable renaming and the second is estimating probabilistic weights for each rule. Given the hardness results mentioned above, most of the literature has concentrated on the second problem. Two dominant approaches for solving the second problem are the
forward-backward algorithm for HMMs~\parciteauthor{Rabiner89} and the inside-outside algorithm for PCFGs~\parciteauthor{Baker79,LariY90}.


In this work we address the first problem. Due to the hardness results regarding learning probabilistic grammars using membership and equivalence queries (\query{mq}\ and \query{eq}) we use structured membership queries and structured equivalence queries (\query{smq}\ and \query{seq}), as was done by~\cite{Sakakibara88} for learning context-free grammars. \emph{Structured strings}, proposed by~\parciteauthor{LevyJ78}, are strings over the given alphabet that includes parentheses that indicate the structure of a possible derivation tree for the string. One can equivalently think about a structured string as a derivation tree in which all nodes but the leaves are marked with $?$, namely an \emph{unlabeled derivation tree}. 

It is known that the set of derivation trees of a given CFG constitutes a \emph{regular tree-language}, where a regular tree-language is a tree-language that can be recognized by a \emph{tree automaton}. 
\cite{Sakakibara88} has generalized Angluin's \staralg{L}\ algorithm (for learning regular languages using \query{mq}\ and \query{eq}) to learning a tree automaton, and provided a polynomial learning algorithm for CFGs using \query{smq}\ and \query{seq}.
Let $\deriv(\grmr{G})$ denote the set of derivation trees of a CFG $\grmr{G}$, and $\struct(\deriv(\grmr{G}))$ the set of unlabeled derivation trees (namely the structured strings of $\grmr{G}$). 
While a membership query (\query{mq}) asks whether a given string $w$ is in the unknown grammar $\grmr{G}$, 
a structured membership query (\query{smq}) asks whether a structured string $s$ is in   $\struct(\deriv(\grmr{G}))$ and a structured equivalence query (\query{seq}) answers whether the queried CFG $\grmr{G}'$ is structurally equivalent to the unknown grammar $\grmr{G}$, and accompanies a negative answer with a structured string $s'$ in the symmetric difference of  $\struct(\deriv(\grmr{G}'))$ and $\struct(\deriv(\grmr{G}))$. 

In our setting, since we are interested in learning probabilistic grammars, an \query{smq}\ on a structured string $s$ is answered by a weight $p\in[0,1]$ standing for the probability for $\grmr{G}$ to generate $s$, and a negative answer to an \query{seq}\ is accompanied by a structured string $s$ such that $\grmr{G}$ and $\grmr{G}'$ generate $s$ with different probabilities (up to a predefined error margin) along with  the probability $p$ with which the unknown grammar $\grmr{G}$ generates $s$. 


\cite{Sakakibara88} works with tree automata to model the derivation trees of the unknown grammars.
In our case the automaton needs to associate a weight with every tree (representing a structured string). We choose to work with the model of \emph{multiplicity tree automata}. A multiplicity tree automaton (MTA) associates with every tree a value from a given field $\mathbb{K}$. An algorithm for learning multiplicity tree automata, to which we refer as \staralg{M}, was developed in~\parciteauthor{habrard2006learning,drewes2007query}.\footnote{Following a learning algorithm developed for multiplicity word automata~\parciteauthor{BergadanoV96}.} 

A probabilistic grammar is a special case of a weighted grammar and~\parciteauthor{abney1999relating,smith2007weighted} have shown that  convergent weighted CFGs (WCFG) where all weights are non-negative and probabilistic CFGs (PCFGs) are equally expressive.\footnote{The definition of \emph{convergent} is deferred to the preliminaries.} We thus might expect to be able to use the learning algorithm \staralg{M}\ to learn an MTA corresponding to a WCFG, and apply this conversion  to the result, in order to obtain the desired PCFG. However, as we show in  Proposition~\ref{prop:needPMTAs}, there are probabilistic languages for which applying the \staralg{M}\ algorithm results in an MTA with negative weights. Trying to adjust the algorithm to learn a positive basis may encounter the issue that for some PCFGs,  no finite subset of the infinite Hankel Matrix spans the entire space of the function, as we show in Proposition~\ref{prop:pcfg-no-finite-rank}.\footnote{The definition of the Hankel Matrix and its role in learning algorithms appears in the sequel.}  To overcome these issues we restrict attention to structurally unambiguous grammars (SUCFG, see section \ref{sec:sucfg}), which as we show, can be modeled using co-linear multiplicity automata (defined next).


We develop a polynomial learning algorithm, which we term \staralg{C}, that learns a restriction of MTA, which we term \emph{co-linear multiplicity tree automata} (CMTA). We then show that a CMTA for a probabilistic language can be converted into a PCFG, thus yielding a complete algorithm for learning SUPCFGs using \query{smq} s and \query{seq} s as desired. 


As a proof-of-concept, in Section \ref{sec:demonstration} we exemplify our algorithm by applying it to a small data-set of genomic data. 

Due to lack of space all proofs are deferred to appendix (App.~B). The appendix also contains (i) a complete running example (App.~A) and (ii)
supplementary material for the demonstration section (App.~C).

\section{Preliminaries}
 

This section provides the  definitions required for  \emph{probabilistic grammars} -- the object we design a learning algorithm for,
and \emph{multiplicity tree automata}, the object we use in the learning algorithm.
\subsection{Probabilistic Grammars}\label{subsec:pcfgs}

Probabilistic grammars are a special case of context free grammars 
where each production rule has a weight in the range $[0,1]$ and for each non-terminal, the sum of weights of its productions is one. 

	A \emph{context free grammar} (CFG) is a quadruple $\grmr{G}=\langle \ensuremath{\mathcal{V}},\Sigma,R,S\rangle$, where
	$\ensuremath{\mathcal{V}}$ is a finite non-empty set of symbols called  \emph{variables} or \emph{non-terminals},
	$\Sigma$ is a finite non-empty set of symbols called the \emph{alphabet} or the \emph{terminals},
	$R\subseteq \ensuremath{\mathcal{V}}\times (\ensuremath{\mathcal{V}}\cup\Sigma)^{*}$ is a relation between variables and strings over $\ensuremath{\mathcal{V}}\cup\Sigma$, called the  \emph{production rules}, and $S\in \ensuremath{\mathcal{V}}$ is a special variable called the \emph{start variable}.
	We assume the reader is familiar with the standard definition of CFGs and of derivation trees.
We say that $S\transderives{} w$ for a string $w\in\Sigma^*$ if there exists a derivation tree $t$ such that all leaves are in $\Sigma$ and when concatenated from left to right they form $w$. That is, $w$ is the \emph{yield} of the tree $t$. In this case we also use the notation $S\transderives{t} w$.
A CFG $\grmr{G}$ defines a set of words over $\Sigma$, the \emph{language generated by} $\grmr{G}$, which  is the set of words $w\in\Sigma^*$ such that $S\transderives{}  w$, and is denoted $\sema{\grmr{G}}$. For simplicity, we assume the grammar does not derive the empty word.

\vspace{-2mm}
\paragraph{Weighted grammars
A \emph{weighted grammar}  (WCFG) is a pair $\tuple{\grmr{G},\theta}$ where $\grmr{G}=\langle \ensuremath{\mathcal{V}},\Sigma,R,S\rangle$ is a CFG and $\theta:R\rightarrow \mathbb{R}$ is a function mapping each production rule to a weight in $\mathbb{R}$.
A WCFG $\grmr{W}=\tuple{\grmr{G},\theta}$ defines a function from words over $\Sigma$ to weights in $\mathbb{R}$. 
The WCFG associates with a derivation tree $t$ its weight, which is defined as 
$\grmr{W}(t)=\prod_{(V\xrightarrow{} \alpha)\in R } \theta(V\xrightarrow{}\alpha)^{\sharp_t(V\xrightarrow{}\alpha)}$
where $\sharp_t(V\xrightarrow{}\alpha)$ is the number of occurrences of the production $V\xrightarrow{}\alpha$ in the derivation tree $t$.
We abuse notation and treat $\semagrmr{\grmr{W}}$ also as a function from $\Sigma^*$ to $\mathbb{R}$  defined as
$\grmr{W}(w)=\sum_{S\transderives{t}w}\grmr{W}(t)$.
That is, the weight of $w$ is the sum of weights of the derivation trees yielding $w$, and if $w\notin\sema{\aut{G}}$ then $\semagrmr{\grmr{W}}(w)=0$.
If the sum of all derivation trees in $\sema{\grmr{G}}$, namely $\sum_{w\in\sema{\grmr{G}}}\grmr{W}(w)$, is finite we say that $\aut{W}$ is \emph{convergent}. 

\vspace{-2mm}
\paragraph{Probabilistic grammars}
A \emph{probabilistic grammar} (PCFG) is a WCFG 
$\grmr{P}=\tuple{\grmr{G},\theta}$ where $\grmr{G}=\langle \ensuremath{\mathcal{V}},\Sigma,R,S\rangle$ is a CFG and $\theta:R\rightarrow [0,1]$ is a function mapping each production rule of $\grmr{G}$ to a weight in the range $[0,1]$ that satisfies 
$1=\sum_{(V \xrightarrow{} \alpha_i) \in R} \theta(V\xrightarrow{} \alpha_i) $ for every $V\in \ensuremath{\mathcal{V}}$.\footnote{Probabilistic grammars are sometimes called \emph{stochastic grammars (SCFGs)}.}
One can see that if $\grmr{P}$ is a PCFG then  the sum of all derivations equals $1$, thus $\grmr{P}$  is convergent.


\subsection{Word/Tree Series and Multiplicity Automata}\label{sec:mta}
While words are defined as sequences over a given alphabet, trees are defined using a \emph{ranked alphabet},
an alphabet $\Sigma=\{\Sigma_0,\Sigma_1,\ldots,\Sigma_p\}$ which is a  tuple of alphabets $\Sigma_k$ where $\Sigma_0$ is non-empty.
Let $\textsl{Trees}(\Sigma)$ be the set of trees over $\Sigma$, where a node labeled $\sigma\in\Sigma_k$ for $0\leq k \leq p$ has exactly $k$ children. While a \emph{word language} is a function mapping all possible words (elements of $\Sigma^*$) to $\{0,1\}$, a \emph{tree language} is a function from all possible trees (elements of $\textsl{Trees}(\Sigma)$) to $\{0,1\}$. We are interested in assigning each word or tree a non-Boolean value, usually a weight $p\in[0,1]$. Let $\mathbb{K}$ be a field. We are interested in functions mapping words or trees to values in $\mathbb{K}$. A function from $\Sigma^*$ to $\mathbb{K}$ is  called a \emph{word series}, and a function from $\textsl{Trees}(\Sigma)$ to $\mathbb{K}$ is referred to as a \emph{tree series}.

\emph{Word automata} are machines that recognize word languages, i.e. they define a function from $\Sigma^*$ to $\{0,1\}$.
\emph{Tree automata} are machines that recognize tree languages, i.e. they define a function from $\textsl{Trees}(\Sigma)$ to $\{0,1\}$.
\emph{Multiplicity word automata} (MA) are machines to implement word series, i.e. they define a function from $\Sigma^*$ to $\mathbb{K}$.
\emph{Multiplicity tree automata} (MTA) are machines to implement tree series, i.e. they define a function from $\textsl{Trees}(\Sigma)$ to $\mathbb{K}$.
Multiplicity automata can be thought of as an algebraic extension of automata, in which reading an input letter is implemented by matrix multiplication.
In a multiplicity word automaton with dimension $m$ over alphabet $\Sigma$, for each $\sigma\in\Sigma$ there is an $m$ by $m$ matrix, $\mu_\sigma$, whose entries are values in $\mathbb{K}$ where intuitively the value of entry $\mu_\sigma(i,j)$ is the weight of the passage from state $i$ to state $j$. The definition of multiplicity tree automata is a bit more involved; it makes use of multilinear functions as defined next. 

\vspace{-2mm}
\paragraph{Multilinear functions}\label{par:multilinear functions}
Let $\mathbb{V}=\mathbb{K}^d$ be the $d$ dimensional vector space over $\mathbb{K}$. Let $\eta : \mathbb{V}^k \rightarrow \mathbb{V}$ be a $k$-linear function.
We can represent $\eta$ by a $d$ by $d^k$ matrix over $\mathbb{K}$. For instance, if $\eta : \mathbb{V}^3 \rightarrow \mathbb{V}$ and $d=2$ (i.e. $\mathbb{V} = \mathbb{K}^2$) then $\eta$ can be represented by the $2\times 2^3$ matrix $M_\eta$ provided in Fig~\ref{fig:mult-aut-matrices} where $c^{i}_{j_1 j_2 j_3} \in \mathbb{K}$ for $i,j_1,j_2,j_3\in\{1,2\}$. 
Then $\eta$, a function taking $k$ parameters in $\mathbb{V}=\mathbb{K}^d$, can be computed by multiplying the matrix $M_\eta$ with a vector for the parameters for $\eta$. Continuing this example, given the parameters $\textbf{x} = (x_1 \ \ x_2)$, $\textbf{y} = (y_1 \  \ y_2)$, $\textbf{z} = (z_1\ \  z_2)$ the value
$\eta(\textbf{x},\textbf{y},\textbf{z})$ can be calculated using the multiplication $M_\eta P_{xyz}$ where the vector $P_{xyz}$  of size $2^3$ is provided in Fig~\ref{fig:mult-aut-matrices}.
\begin{figure}

	\scalebox{.7}{\small{
			\begin{tabular}{l@{\quad}l}
				$M_\eta = \begin{pmatrix}
				c^1_{{111}} & c^1_{{112}}& c^1_{{121}} & c^1_{{122}} & c^1_{{211}} & c^1_{{212}}& c^1_{{221}} & c^1_{{222}} \\[1mm]
				c^2_{{111}} & c^2_{{112}}& c^2_{{121}} & c^2_{{122}} & c^2_{{211}} & c^2_{{212}}& c^2_{{221}} & c^2_{{222}} 
				\end{pmatrix}$
				&
				$P_{xyz} =  \begin{pmatrix}
				x_1 y_1 z_1 \\
				x_1 y_1 z_2 \\
				x_1 y_2 z_1 \\
			
			
			
			
				\ldots \\
				x_2 y_2 z_2 \\
				\end{pmatrix}$
			\end{tabular}
	}}
	\commentout{
	\scalebox{.8}{\small{
			\begin{tabular}{l@{\quad}l}
				$M_\eta = \begin{pmatrix}
				c^1_{{111}} & c^1_{{112}}& c^1_{{121}} & c^1_{{122}} & c^1_{{211}} & c^1_{{212}}& c^1_{{221}} & c^1_{{222}} \\[1mm]
				c^2_{{111}} & c^2_{{112}}& c^2_{{121}} & c^2_{{122}} & c^2_{{211}} & c^2_{{212}}& c^2_{{221}} & c^2_{{222}} 
				\end{pmatrix}$
				&
				$P_{xyz} =  \begin{pmatrix}
				x_1 y_1 z_1 \\
				x_1 y_1 z_2 \\
				x_1 y_2 z_1 \\
			
			
			
			
				\ldots \\
				x_2 y_2 z_2 \\
				\end{pmatrix}$
			\end{tabular}
	}}}
	\caption{A matrix $M_\eta$ for a multi-linear fuction $\eta$ and a vector $P_{xyz}$ for the respective $3$ parameters.
	
	}\label{fig:mult-aut-matrices}
\end{figure} 
In general, if $\eta : \mathbb{V}^k \rightarrow \mathbb{V}$ is such that $\eta(\textbf{x}_1,\textbf{x}_2,\ldots,\textbf{x}_k) = \textbf{y}$ and $M_\eta$, the matrix representation of $\eta$,  is defined using the constants $c^{i}_{j_1 j_2 \ldots j_k}$ then 

\[\textbf{y}[i] = \hspace{-1em} \sum_{\left\{(j_1,j_2,\ldots,j_k)\in \{1,2,\ldots,d\}^k\right\}} \hspace{-1em} c^i_{j_1j_2\ldots j_k} \, \textbf{x}_1[j_1]\, \textbf{x}_2[j_2]\, \cdots \,\textbf{x}_k[j_k]\phantom{------}\qquad\qquad\]
\begin{figure} 
	\scalebox{.8}{
	    \hspace{10mm}\includegraphics[scale=0.8,page=8, clip, trim=2cm 22.5cm 9cm 1.8cm]{figures.pdf}
		\commentout{
			\begin{tabular}{cc}
				$\lambda=\begin{pmatrix}1\\0
				\end{pmatrix}$ \ \ \ 
				$\mu_{a}= \begin{pmatrix}1\\1
				\end{pmatrix}$\\ \quad\vspace{0mm} \\
				$\mu_{b} = \begin{pmatrix}
				0 & 1 & 1 & 0 \\[1mm]
				0 & 0 & 0 & 1 
				\end{pmatrix}$
				
				\\ \quad\vspace{3mm} \\
				\begin{tikzpicture}
				\tikzstyle{myarrow}=[line width=.5mm,draw=#1,-triangle 45,postaction={draw, line width=4mm, shorten >=5mm, -}]
				\node[shape=circle, draw=none] (a1) at (2, 1) {$a$};
				\node[] (a1v) at (3.5, 1) {${\biword{1}{1}}$};
				\node[] (a2v) at (1.5, 1) {${\biword{1}{1}}$};
				\node[shape=circle, draw=none]  (a2) at (3, 1) {$a$};
				\node[shape=circle, draw=none] (a3) at (3.65, 2.0) {$a$};
				\node[] (a3v) at (4.10, 2.0) {${\biword{1}{1}}$};
				\node[shape=circle, draw=none]  (b1) at (2.5, 2.0) {$b$};
				\node[] (a3v) at (2.0, 2.0) {${\biword{2}{1}}$};
				\node[shape=circle, draw=none]  (b2) at (3, 3) {$b$};
				\node[] (b2v) at (2.5, 3) {${\biword{3}{1}}$};
				\draw (b2) -- (a3);
				\draw (b2) -- (b1);
				\draw (b1) -- (a1);
				\draw (b1) -- (a2);
				\end{tikzpicture}
	\end{tabular}}}
	\caption{(I.i) An MTA $\aut{M}=((\Sigma_0,\Sigma_2),\mathbb{R},2,\mu,\lambda)$
		where    ${\Sigma_0=\{a\}}$ and ${\Sigma_2=\{b\}}$  implementing a tree series that returns the number of leaves in the tree. 
		(I.ii) a tree where a node $t$ is annotated by $\mu(t)$. Since $\mu(t_\epsilon)=\biword{3}{1}$, 
		where $t_\epsilon$ is the root, the value of the entire tree is  $\lambda\cdot\biword{3}{1}=3$.
	 (II) a derivation tree and its corresponding skeletal tree.}\label{fig:MTA}\label{fig:structured-string}
\end{figure}


\paragraph{Multiplicity tree automata}
A \emph{multiplicity tree automaton} (MTA) is a tuple $\aut{M}=(\Sigma,\mathbb{K},d,\mu,\lambda)$ where $\Sigma=\{\Sigma_0,\Sigma_1,\ldots,\Sigma_p\}$ is the given ranked alphabet, $\mathbb{K}$ is the respective field, $d$ is a non-negative integer called the  automaton \emph{dimension}, $\mu$ and $\lambda$ are  the transition and output function, respectively, whose types are defined next.
Let $\mathbb{V}=\mathbb{K}^d$. Then  $\lambda$ is an element of $\mathbb{V}$, namely a $d$-vector over $\mathbb{K}$.  Intuitively, $\lambda$ corresponds to the final  values of the ``states'' of $\aut{M}$. The transition function $\mu$ maps each element $\sigma$  of $\Sigma$ to a dedicated transition function $\mu_\sigma$ such that given ${\sigma \in \Sigma_k}$ for ${0 \leq k \leq p}$ then $\mu_\sigma$ is a $k$-linear function from $\mathbb{V}^k$ to $\mathbb{V}$. 
The transition function $\mu$ induces a function from $\textsl{Trees}(\Sigma)$ to $\mathbb{V}$, defined as follows.
If $t=\sigma$ for some $\sigma\in \Sigma_0$, namely $t$ is a tree with one node which is a leaf, then $\mu(t)=\mu_\sigma$ (note that $\mu_\sigma$ is a vector in $\mathbb{K}^d$ when $\sigma\in\Sigma_0$). 
If $t=\sigma(t_1,\ldots,t_k)$, namely $t$ is a tree with root $\sigma\in \Sigma_k$ and children $t_1,\ldots,t_k$ then $\mu(t)=\mu_\sigma(\mu(t_1),\ldots,\mu(t_k))$. 
The automaton $\aut{M}$ induces a total function from $\textsl{Trees}(\Sigma)$ to $\mathbb{K}$ defined as follows $\aut{M}(t)=\lambda\cdot \mu(t)$.
Fig.~\ref{fig:MTA}(I.i) provides an example of an MTA and the value for a computed tree Fig.~\ref{fig:MTA}(I.ii). 





\paragraph{Contexts}
In the course of the algorithm we need a way to compose trees, more accurately we compose trees with \emph{contexts} as defined next.
Let $\Sigma=\{\Sigma_0,\Sigma_1,\ldots,\Sigma_p\}$ be a ranked alphabet. Let $\diamond$ be a symbol not in $\Sigma$. 
We use $\textsl{Trees}_\diamond(\Sigma)$ to denote all non-empty trees over $\Sigma' = \{ \Sigma_0 \cup \{\diamond\}, \Sigma_1,\ldots, \Sigma_p\}$  in which $\diamond$ appears exactly once.
We refer to an element of $\textsl{Trees}_\diamond(\Sigma)$ as a \emph{context}. Note that  at most one child of any node in a context $c$ is a context; the other ones are pure trees (i.e. elements of $\textsl{Trees}(\Sigma))$.
Given a tree ${t\in \textsl{Trees}(\Sigma)}$ and context $c\in \textsl{Trees}_\diamond(\Sigma)$ we use $\contextConcat{c}{t}$ for the tree $t'\in\textsl{Trees}(\Sigma)$ obtained from $c$ by replacing $\diamond$ with $t$. 




\paragraph{Structured tree languages/series}
Recall that our motivation is to learn a word (string) series rather than a tree series, and due to hardness results on learning CFGs and PCFGs we resort to using \emph{structured strings} which are strings with parentheses exposing the structure of a derivation tree for the corresponding trees. 
These are defined formally as follows (and depicted in Fig.~\ref{fig:structured-string} (II)).
A \textit{skeletal alphabet} is a ranked alphabet in which we use a special symbol $?\notin \Sigma_0$ and for every $0<k\leq p$ the set $\Sigma_{k}$ consists only of the symbol $?$. Let $t\in\textsl{Trees}(\Sigma)$, the skeletal description of $t$, denoted by $\skel(t)$, is a tree with the same topology as $t$, in which the symbol in all internal nodes is $?$, and the symbols in all leaves are the same as in $t$. Let $T$ be a set of trees. The corresponding skeletal set, denoted $\skels(T)$ is $\{\skels(t)~|~t\in T\}$.
Going from the other direction, given a skeletal tree $s$ we use $\ensuremath\mathsf{T}(s)$ for the set $\{t\in T~|~\skel(t)= s\}$.

A tree language over a skeletal alphabet is called a \textit{skeletal tree language}. And a mapping from skeletal trees to $\mathbb{K}$ is called a \emph{skeletal tree series}. 
Let $\treesrs{T}$  denote a tree series mapping trees in $\textsl{Trees}(\Sigma)$ to $\mathbb{K}$. 
By abuse of notations, given a skeletal tree, we use $\treesrs{T}(s)$ for the sum of values $\treesrs{T}(t)$ for every tree $t$ of which $s=\skel(t)$.
That is,
$\treesrs{T}(s)=\sum_{t\in\ensuremath\mathsf{T}(s)}\treesrs{T}(t)$.
Thus, given a tree series $\treesrs{T}$ (possibly generated by a WCFG or an MTA) we can treat $\treesrs{T}$ as a skeletal tree series.


\section{From Positive MTAs to PCFGs}\label{sec:CMTA2PCFG}
 
Our learning algorithm for probabilistic grammars builds on the relation between WCFGs with positive weights and PCFGs~\parciteauthor{abney1999relating,smith2007weighted}. In particular, we first establish that a \emph{positive multiplicity tree automaton} (PMTA), which is a multiplicity tree automaton (MTA) where all weights are positive, can be transformed into an equivalent  WCFG $\grmr{W}$.
That is, we  show that  a given PMTA $\aut{A}$  over a skeletal alphabet can be converted into a WCFG $\grmr{W}$ such that for every structured string $s$ we have that $\aut{A}(s)=\aut{W}(s)$. 
If the PMTA defines a convergent tree series (namely the sum of weights of all trees is finite) then so will the constructed WCFG. 
Therefore, given that the WCFG describes a probability distribution, we can apply the transformation of WCFG to a PCFG~\parciteauthor{abney1999relating,smith2007weighted} to yield a PCFG $\grmr{P}$ such that $\grmr{W}(s)=\grmr{P}(s)$, obtaining the desired PCFG for the unknown tree series.

\paragraph{Transforming a PMTA into WCFG}
Let $\aut{A}=(\Sigma,\mathbb{R}_+,d,\mu,\lambda)$ be a PMTA over the skeletal alphabet $\Sigma=\{\Sigma_0,\Sigma_1,\ldots,\Sigma_p\}$. We define a WCFG $\grmr{W}_\aut{A}=(\grmr{G}_\aut{A},\theta)$ for $\grmr{G}_{\aut{A}}=(\ensuremath{\mathcal{V}},\Sigma_{0},R,S)$ as provided in Fig.~\ref{fig:eqs-pmta-to-pcfg} where $c^i_{i_{1},i_{2},...,i_{p}}$ is the respective coefficient in the matrix corresponding to $\mu_?$ for $?\in\Sigma_p$.
\begin{figure}[t]
	\centering
	\scalebox{.85}{	
		{\framebox[1\width]
		
		
		
		
		
		
		
		
		
				{\small{
					$\begin{array}{l@{ }l}
					\ensuremath{\mathcal{V}}= \{S\}\cup\{V_{i}~|~1\leq i\leq d\} &    \\
					R =  \{  S\rightarrow V_{i} ~|~1\leq i\leq d\}\ \cup &   \phantom{..} \theta( S\rightarrow V_{i}) = \lambda[i] \\
					\phantom{R = }\{  V_{i}\rightarrow \sigma  ~|~1\leq i\leq d,\ \sigma\in\Sigma_0 \}\  \cup  &  \phantom{..} \theta( V_{i}\rightarrow \sigma ) = \mu_\sigma[i] \\
					\phantom{R = } \left\{ V_{i}\rightarrow V_{i_{1}}V_{i_{2}}...V_{i_{k}} ~\left|~\begin{array}{l} 1\leq i,i_j \leq d, \\ \text{ for } 1\leq j\leq k \end{array}\right.\right\} & 
					\begin{array}{l} \theta(V_{i}\rightarrow V_{i_{1}}V_{i_{2}}...V_{i_{k}}) =  \\ \phantom{------} c^i_{i_{1},i_{2},...,i_{p}}  \end{array}\
					 \\		
					 \\					 
					\end{array}$}}		}}
	\caption{Transforming a PMTA into a PCFG}\label{fig:eqs-pmta-to-pcfg}
\end{figure}
The following proposition states that the transformation preserves the weights.
\begin{proposition}\label{prop:equiv1}
	$\grmr{W}(t)=\mathcal{A}(t)\quad$ for every $t\in \textsl{Trees}(\Sigma)$.
\end{proposition}

In Section~\ref{sec:learning-CMTAs}, Thm.~\ref{thm:bounds}, we show that we can learn a PMTA for a SUWCFG in polynomial time using a polynomial number of queries (see exact bounds there), thus obtaining the following result.
 \begin{corollary}\label{cor:learnSUWCFG}
	SUWCFGs can be learned in polynomial time using \query{smq} s and 
	\query{seq} s, where the number of \query{seq} s is bounded by the number of non-terminal symbols.
\end{corollary}

The overall learning time for SUPCFG relies, on top of Corollary~\ref{cor:learnSUWCFG}, on the complexity of 
converting a WCFG into a PCFG~\parciteauthor{abney1999relating}, for which an exact bound is not provided, but the method is reported to converge quickly~\cite[\S 2.1]{smith2007weighted}.





\section{Learning Struc. Unamb. PCFGs}\label{sec:-tow-learning-CMTAs}
 

In this section we discuss the setting of the algorithm, the ideas behind Angluin-style learning algorithms, and the issues with using current algorithms to learn PCFGs.
As in \staralg{G} (the algorithm for CFGs~\parciteauthor{Sakakibara88}), we assume an oracle that can answer two types of queries: \emph{structured membership queries} (\query{smq}) and \emph{structured equivalence queries} (\query{seq}) regarding the unknown regular tree series $\treesrs{T}$ (over a given ranked alphabet $\Sigma$). Given a structured string $s$, the query $\query{smq}(s)$ is answered with the value $\treesrs{T}(s)$. Given an automaton $\aut{A}$ the query $\query{seq}(\aut{A})$  is answered ``yes'' if $\aut{A}$ implements the skeletal tree series $\treesrs{T}$ and otherwise the answer is a pair $(s,\treesrs{T}(s))$ where $s$ is a  structured string for which $\treesrs{T}(s)\neq \aut{A}(s)$ (up to a  predefined error). 


Our starting point is the learning algorithm \staralg{M}~\parciteauthor{habrard2006learning} which learns MTA using \query{smq} s and \query{seq} s.
 First we explain the idea behind this and similar algorithms, next the issues with applying it as is for learning PCFGs, then the idea behind restricting attention to strucutrally unambiguous grammars, and finally the algorithm itself.


\paragraph{Hankel Matrix}
All the generalizations of \staralg{L}\ (the algorithm for learning regular languages using \query{mq} s and \query{eq} s, that introduced this learning paradigm~\parciteauthor{Angluin87}) 
share a general idea that can be explained as follows. 
A word or tree language as well as word or tree series can be represented by its Hankel Matrix. 
The Hankel Matrix has infinitely many rows and infinitely many columns. In the case of word series both rows and columns correspond to an infinite enumeration $w_0,w_1,w_2,\ldots$ of words over the given alphabet. In the case of tree series, the rows correspond to an infinite enumeration of trees $t_0,t_1,t_2,\ldots$ (where $t_i\in\textsl{Trees}(\Sigma)$) and the columns to an infinite enumeration of contexts $c_0,c_1,c_2,\ldots$ (where $c_i\in\textsl{Trees}_{\diamond}(\Sigma)$). The entry $\hm{H}(i,j)$ 
holds in the case of words the value for the word $w_i\cdot w_j$ and in the case of trees the value of the tree $\contextConcat{c_j}{t_i}$.
If the series is \emph{regular} there should exists a finite number of rows in this infinite matrix, which we term \emph{basis} such that all other rows can be represented using rows in the basis. In the case of \staralg{L}, and \staralg{G} (that learn word-languages and tree-languages, resp.) rows that are not in the basis should be equivalent to rows in the basis. In the case of \staralg{M} (that learns tree-series) rows not in the basis should be expressible as a linear combination of rows in the basis. In our case, in order to apply the PMTA to PCFG conversion we need the algorithm to find a \emph{positive linear combination} of rows to act as the basis. In all cases we would like the basis to be \emph{minimal} in the sense that no row in the basis is expressible using other rows in the basis. This is since the size of the basis derives the dimension  of the automaton, and obviously we prefer smaller automata.

\paragraph{Positive linear spans}
An interest in \emph{positive linear combinations} occurs also in the research community studying convex cones and derivative-free optimizations and a theory of positive linear combinations has been developed~\parciteauthor{cohen1993nonnegative,Regis2016}.\footnote{Throughout the paper we use the terms \emph{positive} and \emph{nonnegative} interchangeably.} We need the following definitions and results.

The \emph{positive span} of a finite set of vectors $S=\{v_{1},v_{2},...,v_{k}\}\subseteq\mathbb{R}^{n}$ is defined as follows:
\begin{equation*}
\textsl{span}_{+}(S)=\{\lambda_{1}\cdot v_{1}+\lambda_{2}\cdot v_{2}+...+\lambda_{k}\cdot v_{k} ~|~ \lambda_{i}\geq 0, \forall 1\leq i\leq k\}
\end{equation*}
A set of vectors $S=\{v_{1},v_{2},...,v_{k}\}\subseteq\mathbb{R}^{n}$ is \emph{positively dependent} if some $v_{i}$ is a positive combination of the other vectors; otherwise, it is \emph{positively independent}. 
Let $A\in\mathbb{R}^{m\times n}$. We say that $A$ is \emph{nonnegative} if all of its elements are nonnegative.  The \emph{nonnegative column (resp. row) rank}  of $A$, denoted $\ensuremath{\textsl{c-rank}_{+}}(A)$ (resp. $\ensuremath{\textsl{r-rank}_{+}}(A)$), is defined as the smallest nonnegative integer $q$ for which there exist a set of column- (resp. row-) vectors $V=\{v_{1},v_{2},...,v_{q}\}$  in $\mathbb{R}^{m}$ such that every column (resp. row) of $A$ can be represented as a positive combination of $V$.
It is known  that $\ensuremath{\textsl{c-rank}_{+}}(A)=\ensuremath{\textsl{r-rank}_{+}}(A)$ for any matrix $A$~\parciteauthor{cohen1993nonnegative}. Thus one can  freely use $\ensuremath{\textsl{rank}_{+}}(A)$ for \emph{positive rank}, to refer to either one of these.


\paragraph{Issues with positive spans}

The first question that comes to mind, is whether we can use the \staralg{M}\ algorithm as is to learn a positive tree series. We show that this is not the case.
In particular, there are positive tree series for which applying the \staralg{M}\ algorithm results in an MTA with negative weights. Moreover, this holds also if
we consider word (rather than tree) series, and if we restrict the weights to be probabilistic (rather than simply positive).


\begin{proposition}\label{prop:needPMTAs}
	There exists a probabilistic word series for which the \staralg{M}\ alg. may return an MTA with negative weights.
\end{proposition}
The proof shows this is the case for the word series over alphabet ${\Sigma=\{a,b,c\}}$ which assigns   
the following six strings: $aa$, $ab$, $ac$, $ba$, $cb$, $cc$ probability of $\frac{1}{6}$ each, and probability $0$ to all other strings.

Hence, we turn to ask whether 
we can adjust the algorithm \staralg{M}\ to learn a positive basis. 
We note first that working with positive spans is much trickier than working with general spans, since for $d\geq 3$ there
is no bound on the size of a positively independent set in  $\mathbb{R}_+^d$~\parciteauthor{Regis2016}. To apply the ideas of the Angluin-style query learning algorihtms we 
 need the Hankel Matrix (which is infinite) to contain a finite sub-matrix with the same rank. 
Unfortunately, as we show next,
there exists a probabilistic (thus positive) tree series  $\treesrs{T}$
that can be recognized by a PMTA, but none of its finite-sub-matrices span the entire space of $\hm{H}_\treesrs{T}$.

\begin{proposition}\label{prop:pcfg-no-finite-rank}
	There exists a PCFG $\grmr{G}$ s.t. the Hankel Matrix
	$H_\grmr{G}$ corresponding to its tree-series $\treesrs{T}_G$ has the property that
	no finite number of rows positively spans the entire matrix.
\end{proposition}

The proof shows this is the case for the following PCFG:
$$\begin{array}{l@{\ \longrightarrow\ }l}
N_{1}& aN_{1}~[\frac{1}{2}]\ \mid\  aN_{2}~[\frac{1}{3}]\ \mid\  aa~[\frac{1}{6}]\\[2mm]
N_{2}& aN_{1}~[\frac{1}{4}]\ \mid\  aN_{2}~[\frac{1}{4}]\ \mid\  aa~[\frac{1}{2}]
\end{array}$$



\subsection{Focusing on Strucutrally Unambiguous CFGs}\label{sec:sucfg}
To overcome these obstacles we restrict attention to strucutrally unambiguous CFGs (SUCFGs) and their weighted/probabilistic versions (SUWCFGs/SUPCFGs).
A context-free grammar is termed \emph{ambiguous} if there exists more than one derivation tree for the same word.
We  term a CFG \emph{structurally ambiguous} if there exists more than one
derivation tree with the same structure for the same word.
A context-free  language is termed \emph{inherently ambiguous}   if it cannot be derived by an unambiguous CFG.
 Note that a CFG which is unambiguous is also structuraly unambiguous, while the other direction is not necessarily true.
{For instance, 
	the language $\{a^n b^n c^md^m~|~ n\geq 1, m\geq 1\}\cup \{a^n b^m c^md^n~|~ n\geq 1,m\geq 1\}$ which is inherently ambiguous~\cite[Thm.~4.7]{HopcroftUllman79} is not inherently structurally ambiguous.} 
Therefore
we have relaxed the classical unambiguity requirement. 

\paragraph{The Hankel Matrix and MTA for SUPCFG}
Recall that the Hankel Matrix considers skeletal trees. Therefore if a word has more than one derivation tree with the same
structure, the respective entry in the matrix holds the sum of weights for all derivations. This makes it harder for the learning algorithm
to infer the weight of each tree separately. By choosing to work with strucutrally unambiguous grammars, we overcome this diffictulty
as an entry corresponds to a single derivation tree. 

To discuss properties of the Hankel Matrix for an SUPCFG we need the following definitions.
Let ${H}$ be a matrix, $t$ a tree (or row index) $c$ a context (or column index), $T$ a set of trees (or row indices) and $C$ a set of contexts (or column indices).
We use ${H}[t]$ (resp. ${H}[c]$) for the row (resp. column) of ${H}$ corresponding to $t$ (resp. $c$).
Similarly we use ${H}[T]$ and ${H}[C]$ for the corresponding sets of rows or columns. Finally, we use  ${H}[t][C]$ for the restriction of ${H}$ to row $t$ and columns $[C]$.

Two vectors, $v_{1},v_{2}\in\mathbb{R}^{n}$ are co-linear with a scalar ${\alpha\in\mathbb{R}}$ for some $\alpha\neq 0$ iff $v_{1}=\alpha\cdot v_{2}$.
 Given a matrix $H$, and two trees $t_1$ and $t_2$, we say that $t_{1}\treesColin{\alpha}{H} t_{2}$ iff ${H}[t_{1}]$ and ${H}[t_{2}]$ are co-linear, with scalar $\alpha\neq 0$. That is, $H[t_{1}]=\alpha\cdot H[t_{2}]$. Note that if $H[t_{1}]=H[t_{2}]=\bar{0}$, then $t_{1}\treesColin{\alpha}{H} t_{2}\treesColin{\alpha}{H} t_{1}$ for every $\alpha>0$.
We say that $t_{1}\treesEquiv{H} t_{2}$ if $t_{1}\treesColin{\alpha}{H} t_{2}$ for some $\alpha\neq 0$.  It is not hard to see that $\treesEquiv{H}$ is an equivalence relation.

The following proposition states that in the Hankel Matrix of an SUPCFG, the rows of trees that are rooted by the same non-terminal
 are co-linear.
\begin{proposition}\label{prop:colinearity}
	Let $\hm{H}$ be the Hankel Matrix of an SUPCFG. 
	Let $t_{1},t_{2}$ be derivation trees rooted by the same non-terminal. Assume $\mathbb{P}(t_{1}),\mathbb{P}(t_{2})>0$.
	Then $t_{1}\treesColin{\alpha}{\hm{H}} t_{2}$ for some $\alpha\neq 0$.
\end{proposition}

We can thus conclude that the number of equivalence classes of $\equiv_{H}$ for an SUPCFG is finite and
bounded by the number of non-terminals plus one (for the zero vector). 
\begin{corollary}\label{cor:finite-equiv-cls}
	The skeletal tree-set for an SUPCFG has a finite number of equivalence classes under $\equiv_{H}$.
\end{corollary}



Next we would like to reveal the restrictions that can be emposed on a PMTA that corresponds to an SUPCFG.
We term an MTA \emph{co-linear} (and denote it CMTA) if in every column of every transition matrix $\mu_\sigma$ there is at most one entry
which is non-negative. 
\begin{proposition}\label{prop:SUWCFGhaveCMTA}

	A CMTA can represent an SUPCFG.
\end{proposition}
The proof relies on showing that a WCFG is strucuturally unambiguous iff it is invertible
and converting an invertible WCFG into a PMTA yields a CMTA.\footnote{A CFG $\grmr{G}=\langle \ensuremath{\mathcal{V}},\Sigma,R,S\rangle$ is said to be
invertible if and only if $A \rightarrow \alpha$ and $B \rightarrow \alpha$ in $R$ implies $A = B$~\parciteauthor{Sakakibara92}.}

\section{The Learning Algorithm}\label{sec:learning-CMTAs}
 

\input{learning}


 




\section{Demonstration}\label{sec:demonstration}
As a demonstration, we apply our algorithm to the learning of gene cluster grammars --- which is an important problem in functional genomics.
A \emph{gene cluster} is a group of genes that are co-locally conserved, not necessarily in the same order, across many genomes~\parciteauthor{winter2016finding}. The gene grammar corresponding to a given gene cluster describes its hierarchical inner structure and the relations between instances of the cluster succinctly;  assists in predicting the functional association between the genes in the cluster; provides insights into the evolutionary history of the cluster; aids in filtering meaningful from apparently meaningless clusters; and provides a natural and meaningful way of visualizing complex clusters. 

PQ trees have been advocated as a representation for gene-grammars~\parciteauthor{booth1976testing,bergeron2008formal}. A PQ-tree represents the possible permutations of a given sequence, and can be constructed in polynomial-time~\parciteauthor{landau2005gene}. 
A PQ-tree is a rooted tree with three types of nodes: {\em P-nodes}, {\em Q-nodes} and leaves. In the gene grammar inferred by a given PQ-tree, the children of a P-node can appear in any order, while the children of a Q-node must appear in either left-to-right or right-to-left order.

However,  the PQ tree model suffers from limited specificity, which often does not scale up to encompass gene clusters that exhibit some rare-occurring permutations.  It also does not model tandem gene-duplications, which are a common event in the evolution of gene-clusters. We exemplify how our algorithm can learn a grammar that addresses both of these problems. Using the more general model of context-free grammar, we can model evolutionary events that PQ-trees cannot, such as tandem gene-duplications. While the probabilities in our PCFGs grant our approach the capability to model rare-occurring permutations (and weighing them as such), thus creating a specificity which PQ-trees lack. 

We give two examples of gene-cluster grammars. The first is a PCFG describing a gene cluster corresponding to a multi-drug efflux pump (MDR). MDR's are used by some bacteria as a mechanism for antibiotic resistance, and hence are the focus of research aimed towards the development of new therapeutic strategies. 
In this example, we exemplify learning of a gene-cluster grammar which models distinctly ordered merge events of sub-clusters in the evolution of this pump. The resulting learned gene-cluster grammar is illustrated in Fig.~\ref{fig:grammar1}. A biological interpretation of the learned grammar, associating the highly probable rules with possible evolutionary events that explain them, is available in Section.~\ref{supp:biogramm}.

Note that, in contrast to the highly specific PCFG learned by our algorithm (Fig.~\ref{fig:grammar1}, top), the PQ-tree constructed for this gene cluster (Fig.~\ref{fig:grammar1}, middle) places all leaves under a single P-node, resulting in a complete loss of specificity regarding conserved gene orders and hierarchical swaps --- this PQ tree will accept all permutations of the four genes, without providing information about which permutations are more probable, as our learned PCFG does. 

In a second example, which is available in Section.~\ref{sec:fimacd_grammar} we exemplify learning of a gene-cluster grammar which models tandem duplication events. The yielded grammar demonstrates learning of an infinite language, with exponentially decaying probabilities. 

\begin{figure}
    \noindent\makebox[\textwidth/2]{
       
       
        \includegraphics[scale=0.8,page=9, clip, trim=2cm 20.5cm 9cm 1.8cm]{figures.pdf}
    }
    \caption{{The PCFG learned from the MDR dataset. Also shown are the most probable tree according to the grammar (left) with $p=0.456$,  a non-probable tree (right) with $p=0.001$, and the PQ-tree (middle) showing a complete lack of specificity.}}
    \vspace{-4mm}
    \label{fig:grammar1}
\end{figure}


\section{Discussion}\label{sec:discussion}
 We have presented algorithms for learning structurally unambiguous PCFGs from a given black-box language model using structured membership and equivalence queries.
To our knowledge this is the first algorithm provided for this question. A recent paper~\parciteauthor{WeissGY19} advocates one can obtain an interpretable model 
of practically black-box models such as recurrent neural networks, using PDFA learning. The present work extends on this and offers obtaining intrepretable models also in cases where the studied
object exhibits non-regular (yet context-free) behavior, as is the case, e.g. in Gene Cluster grammars. 
}

\clearpage




\subsection{Example for a PCFG with an Hankel Matrix with no positive basis}
Next, we would like to show that there exists a PCFG $\grmr{G}$ such that the Hankel Matrix
$H_\grmr{G}$ corresponding to its tree-series $\treesrs{T}_G$ has the property that
no finite number of rows spans the entire matrix.

We first prove the following lemma about positive indepedent sets.


\begin{lemma}\label{lemmaSing}
	Let $B=\{b_{1},b_{2},...,b_{p}\}$ be set of positively independent vectors. 
	Let $\hat{B}$ be a matrix whose rows are the elements of $B$, and let $\alpha$ be a positive vector. 
	Then if $\hat{B}\alpha=b_{i}$ then $\alpha[i]=1$ and $\alpha[j]=0$ for every $j\neq i$.
\end{lemma}

\begin{proof}
	Assume $b_{i}=\hat{B}\alpha$. Then we have:
	\begin{equation*}
	    b_{i}=\hat{B}\alpha=\sum_{j=1}^{p}\alpha_{j}b_{j}=\alpha_{i}b_{i}+\sum_{j\neq i}\alpha_{j}b_{j}
	\end{equation*}
	If $\alpha_{i}<1$ we obtain:
	\begin{equation*}
	    b_{i}(1-\alpha_{i})=\sum_{j\neq i}\alpha_{j}b_{j}
	\end{equation*}
	Which is a contradiction, since $b_{i}\in B$ and thus can't be described as a positive combination of the other elements.
	
	If $\alpha_{i}>1$ we obtain:
	\begin{equation*}
	    \sum_{j\neq i}\alpha_{j}b_{j}+(\alpha_{i}-1)b_{i}=0
	\end{equation*}
	This is a contradiction, since each $b>0$, and each $\alpha_{j}\geq 0$, with $\alpha_{i}>1$.
	
	Hence $\alpha_{i}=1$. Therefore we have:
	\begin{align*}
	    \sum_{j\neq i}\alpha_{j}b_{j}=0
	\end{align*}
	Since $\alpha_{j}\geq 0$, and $b_{j}>0$ the only solution is that $\alpha_{j}=0$ for every $j\neq i$.
\end{proof}

\noindent
We are now ready to prove \claimref{Proposition~\ref{prop:pcfg-no-finite-rank}} which states:
\begin{itemize}
    \item []
	\emph{There exists a PCFG $\grmr{G}$ such that the Hankel Matrix
	$H_\grmr{G}$ corresponding to its tree-series $\treesrs{T}_G$ has the property that
	no finite number of rows spans the entire matrix.}
\end{itemize}

\begin{proof}
Let $\grmr{G}=(\{a\},\{N_{1},N_{2}\},R,N_{1})$ be the following PCFG:
$$\begin{array}{l@{\ \longrightarrow\ }l}
N_{1}& aN_{1}~[\frac{1}{2}]\ \mid\  aN_{2}~[\frac{1}{3}]\ \mid\  aa~[\frac{1}{6}]\\[2mm]
N_{2}& aN_{1}~[\frac{1}{4}]\ \mid\  aN_{2}~[\frac{1}{4}]\ \mid\  aa~[\frac{1}{2}]
\end{array}$$

We say that a tree has a \emph{chain structure} if every inner node is of branching-degree $2$ and has
one child which is a terminal. We say that a tree has a \emph{right-chain structure} (resp. \emph{left-chain structure})
if the non-terminal is always the right (resp. left) child.
Note that all trees in $\sema{G}$ have a right-chain structure (and the terminals are always the letter $a$), and can
be depicted as follows:

\Tree [.? $a$ [.? $a$ [.$\ddots$ $a$ [.? $a$ $a$ ] ] ] ]\vspace{2mm}
Let us denote by $p_{n}$ the total probability of all trees with $n$ non-terminals s.t. the lowest non terminal is $N_{1}$, 
and similarly, let us denote by $q_{n}$ the total probability of all trees with $n$ non-terminals s.t. the lowest non-terminal is $N_{2}$. 

We have that $p_{0}=0$, $p_{1}=\frac{1}{6}$, and  $p_{2}=\frac{1}{12}$. We also have that $q_{0}=0$, $q_{1}=0$ and  $q_{2}=\frac{1}{6}$. 

Now, to create a tree with $n$ non-terminals, we should take a tree with $n-1$ non-terminals, ending with either $N_{1}$ or $N_{2}$, and use the last derivation. So we have:
\begin{align*}
p_{n}&=\frac{1}{2}\cdot p_{n-1}+\frac{1}{4}\cdot q_{n-1}\\
q_{n}&=\frac{1}{3}\cdot p_{n-1}+\frac{1}{4}\cdot q_{n-1}
\end{align*}

We want to express $p_{n}$ only as a function of $p_{i}$ for $i<n$, and similarly for $q_{n}$. Starting with the first equation we obtain:
\begin{align*}
p_{n}&=\frac{1}{2}\cdot p_{n-1}+\frac{1}{4}\cdot q_{n-1}\\
4\cdot p_{n+1}-2\cdot p_{n}&=q_{n}\\
4\cdot p_{n}-2\cdot p_{n-1}&=q_{n-1}
\end{align*}

And from the second equation we obtain:
\begin{align*}
q_{n}&=\frac{1}{3}\cdot p_{n-1}+\frac{1}{4}\cdot q_{n-1}\\
3\cdot q_{n+1}-\frac{3}{4}\cdot q_{n}&=p_{n}\\
3\cdot q_{n}-\frac{3}{4}\cdot q_{n-1}&=p_{n-1}
\end{align*}

Now setting these values in each of the equation, we obtain:

\begin{align*}
4\cdot p_{n+1}-2\cdot p_{n}&=\frac{1}{3}\cdot p_{n-1}+\frac{1}{4}(4\cdot p_{n}-2\cdot p_{n-1})\\
p_{n+1}&=\frac{1}{2}\cdot p_{n}+\frac{1}{12}\cdot p_{n-1}+\frac{1}{16}(4\cdot p_{n}-2\cdot p_{n-1})\\
p_{n+1}&=\frac{1}{2}\cdot p_{n}+\frac{1}{12}\cdot p_{n-1}+\frac{1}{4}\cdot p_{n}-\frac{1}{8}\cdot p_{n-1}\\
p_{n+1}&=\frac{3}{4}\cdot p_{n}-\frac{1}{24}\cdot p_{n-1}
\end{align*}

And:

\begin{align*}
3\cdot q_{n+1}-\frac{3}{4}\cdot q_{n}&=\frac{1}{2}\cdot(3\cdot q_{n}-\frac{3}{4}\cdot q_{n-1})+\frac{1}{4}\cdot q_{n-1}\\
3\cdot q_{n+1}&=\frac{9}{4}\cdot q_{n}-\frac{1}{8}\cdot q_{n-1}\\
q_{n+1}&=\frac{9}{12}\cdot q_{n}-\frac{1}{24}\cdot q_{n-1}=\frac{3}{4}\cdot q_{n}-\frac{1}{24}\cdot q_{n-1}
\end{align*}
Let's denote by $t_{n}$ the probability that $\mathcal{G}$ assigns to $a^{n}$. This probability is:
\begin{equation*}
t_{n}=\frac{1}{6}\cdot p_{n-1}+\frac{1}{2}\cdot q_{n-1}
\end{equation*}
Since $$p_{n-1}=\frac{3}{4}\cdot p_{n-2}-\frac{1}{24}\cdot p_{n-3}$$ and $$q_{n-1}=\frac{3}{4}\cdot q_{n-2}-\frac{1}{24}\cdot q_{n-3}$$ we obtain:
{\small
\begin{align*}
t_{n}=&\frac{1}{6}\cdot(\frac{3}{4}\cdot p_{n-2}-\frac{1}{24}\cdot p_{n-3})+\frac{1}{2}\cdot(\frac{3}{4}\cdot q_{n-2}-\frac{1}{24}\cdot q_{n-3})\\
t_{n}=&\frac{1}{6}\cdot\frac{3}{4}\cdot p_{n-2}-\frac{1}{6}\cdot\frac{1}{24}\cdot p_{n-3}+\frac{1}{2}\cdot\frac{3}{4}\cdot q_{n-2}-\frac{1}{2}\cdot\frac{1}{24}\cdot q_{n-3}\\
t_{n}=&\frac{3}{4}\cdot(\frac{1}{6}\cdot p_{n-2}+\frac{1}{2}\cdot q_{n-2})-\frac{1}{24}\cdot(\frac{1}{6}\cdot p_{n-3}+\frac{1}{2}\cdot q_{n-3})=\\
       =&\frac{3}{4}\cdot t_{n-1}-\frac{1}{24}\cdot t_{n-2}
\end{align*}
}

Hence, overall, we obtain:
\begin{equation*}
t_{n}=\frac{3}{4}\cdot t_{n-1}-\frac{1}{24}\cdot t_{n-2}
\end{equation*}

Now, let $L$ be the skeletal-tree-language of the grammar $\mathcal{G}$, and let $H$ be the Hankel Matrix for this tree set. Note, that any tree $t$ whose structure is not a right-chain, would have $L(t)=0$, and also for every context $c$, $L(\contextConcat{c}{t})=0$. Similarly, every context $c$ who violates the right-chain structure, would have $L(\contextConcat{c}{t})=0$ for every $t$.

Let $T_{n}$ be the skeletal tree for the tree of right-chain structure, with $n$ leaves. We have that $L(T_{1})=0$, $L(T_{2})=\frac{1}{6}$, $L(T_{3})=\frac{1}{4}$, and for every $i>3$ we have $$L(T_{i})=\frac{3}{4}\cdot L(T_{i-1})-\frac{1}{24}\cdot L(T_{i-2}).$$ Let $v_{i}$ be the infinite row-vector of the Hankel matrix corresponding to $T_{i}$. We have that for every $i>3$, $$v_{i}=\frac{3}{4}\cdot v_{i-1}-\frac{1}{24}\cdot v_{i-2}.$$ Assume towards contradiction that there exists a subset of rows that is a positive base and spans the entire matrix $H$.

Let $B$ be the positive base, whose highest member (in the lexicographic order) is the lowest among all the positive bases. Let $v_{r}$ be the row vector for the highest member in this base. Thus, $v_{r+1}\in\posspan{B}$. Hence:
\begin{equation*}
v_{r+1}=\alpha \hat{B}
\end{equation*}
Also, $v_{r+1}=\frac{3}{4}\cdot v_{r}-\frac{1}{24}\cdot v_{r-1}$. Therefore,
\begin{align*}
\frac{3}{4}\cdot v_{r}-\frac{1}{24}\cdot v_{r-1}=\alpha\hat{B}\\
v_{r}=\frac{4}{3}\cdot\alpha\hat{B}+\frac{1}{18}\cdot v_{r-1}
\end{align*}

We will next show that $v_{r-1}$ and $v_r$ are co-linear, which contradicts our choice of $v_r$.
Since $v_{r-1}\in\posspan{B}$ we know $v_{r-1}=\alpha'\hat{B}$ for some $\alpha'$. Therefore, 
\begin{equation*}
v_{r}=(\frac{4}{3}\cdot\alpha+\frac{1}{18}\cdot\alpha')\hat{B}
\end{equation*}
Let $\beta=\frac{4}{3}\cdot\alpha+\frac{1}{18}\cdot\alpha'$. Since $\alpha$ and $\alpha'$ are non-negative vectors, so is $\beta$. And by lemma \ref{lemmaSing}  it follows that for every $i\neq r$:
\begin{equation*}
\beta_{i}=\frac{4\cdot\alpha_{i}}{3}+\frac{\alpha'_{i}}{18}=0
\end{equation*}
Since $\alpha_{i}$ and $\alpha'_{i}$ are non-negative, we have that $\alpha_{i}=\alpha'_{i}=0$.

Since for every $i\neq r$, $\alpha'_{i}=0$, it follows that $v_{r-1}=m\cdot v_{r}$ for some $m\in\mathbb{R}$. 
Now, $m$ can't be zero since our language is strictly positive and all entries in the matrix are non-negative. Thus, $v_{r}=\frac{1}{m}\cdot v_{r-1}$, and $v_{r}$ and $v_{r-1}$ are co-linear. We can replace $v_{r}$ by $v_{r-1}$, contradicting the fact that we chose the base whose highest member is as low as possible.
\end{proof}
\subsection{Example showing a positive rational tree series can be generated by an MTA with negative weights}\label{app:needPMTAs}
We start with the proof of \claimref{Proposition \ref{prop:needPMTAs}} which states that 
	\begin{itemize}
		\item [] 	\emph{There exists a probabilistic word series for which the \staralg{M}\ algorithm may return an MTA with negative weights.}
	\end{itemize}


\begin{proof}
	The first rows of Hankel Matrix for this word series are given in the following figure (all entries not in the figure are $0$).
	One can see that the rows $\epsilon$, $b$, $c$, $ba$ are a positive span of the entire Hankel Matrix. 
	However, the $\staralg{M}$ algorithm may return the MTA spanned by the basis $\epsilon$, $a$, $b$, $aa$. 
	Since the row of $c$ is obtained by substracting the row of $b$ from the row of $a$, this MTA will contain negative weights.
	
	\begin{center}
		\scalebox{.27}
		{\includegraphics{example_table.png}}
	\end{center}
\end{proof}

\subsection{Proofs Regarding the Hankel Matrix for SUWCFGs}
We provide here the proof of \claimref{Proposition~\ref{prop:colinearity}} which states that 

\begin{itemize}
	\item [] 
	\emph{Let $H$ be the Hankel Matrix of an SUWCFG. 
	Let $t_{1},t_{2}$ be derivation trees rooted by the same non-terminal $N_i$. Assume $\mathbb{P}(t_{1}),\mathbb{P}(t_{2})>0$.
	Then $t_{1}\treesColin{\alpha}{H} t_{2}$ for some $\alpha\neq 0$.}
\end{itemize}

\begin{proof}
	Let $c$ be a context. Let $u\diamond v$ be the  yield of the context; that is, the letters with which the leaves of the context are tagged, in a left to right order. $u$ and $v$ might be $\varepsilon$. 
	We denote by $\mathbb{P}_{i}(c)$ the probability of deriving this context, while setting the context location to be $N_{i}$. That is:
	\begin{equation*}
	\mathbb{P}_{i}(c)=\mathbb{P}(S\underset{\mathcal{G}}{\overset{*}{\rightarrow}} u N_{i} v)
	\end{equation*}
	Let $\mathbb{P}(t_{1})$ and $\mathbb{P}(t_{2})$ be the probabilities for deriving the trees $t_{1}$ and $t_{2}$ respectively. So we obtain:
	
	\begin{align*}
	\mathbb{P}(\contextConcat{c}{t_{1}})&=\mathbb{P}_{i}(c)\cdot \mathbb{P}(t_{1})\\
	\mathbb{P}(\contextConcat{c}{t_{2}})&=\mathbb{P}_{i}(c)\cdot \mathbb{P}(t_{2})
	\end{align*}
	So we obtain, for every context $c$, assuming that $P_{i}(c)\neq 0$:
	\begin{equation*}
	\frac{\mathbb{P}(\contextConcat{c}{t_{1}})}{\mathbb{P}(\contextConcat{c}{t_{2}})}=\frac{\mathbb{P}(t_{1})}{\mathbb{P}(t_{2})}
	\end{equation*}
	For a context $c$ s.t. $P_{i}(c)=0$ we obtain that $\mathbb{P}(\contextConcat{c}{t_{1}})=\mathbb{P}(\contextConcat{c}{t_{2}})=0$. So for every context:
	\begin{equation*}
	\mathbb{P}(\contextConcat{c}{t_{1}})=\frac{\mathbb{P}(t_{1})}{\mathbb{P}(t_{2})}\mathbb{P}(\contextConcat{c}{t_{2}})
	\end{equation*}
	So $H[t_{1}]=\alpha\cdot H[t_{2}]$ for $\alpha=\frac{\mathbb{P}(t_{1})}{\mathbb{P}(t_{2})}$, so $H[t_{1}]$ and $H[t_{2}]$ are co-linear, and $t_{1}\treesColin{\alpha}{H} t_{2}$.
\end{proof}

We turn to prove \claimref{Corollary~\ref{cor:finite-equiv-cls}} which states that
\begin{itemize}
	\item []
	\emph{The skeletal tree-set for an SUPCFG has a finite number of equivalence classes under $\equiv_{H}$.}
\end{itemize}
\begin{proof}
	Since the PCFG is structurally unambiguous, it follows that for every skeletal tree $s$ there is a single tagged parse tree $t$ s.t. $\skel(t)=s$. So for every $s$ there is a single possible tagging, and a single possible non-terminal in the root. By Proposition \ref{prop:colinearity} every two trees $s_{1},s_{2}$  which are tagged by the same non-terminal, and in which $\mathbb{P}(s_{1}),\mathbb{P}(s_{2})>0$ are in the same equivalence class under $\equiv_{H}$. There is another equivalence class for all the trees $t\in\textsl{Trees}$ s.t. $\mathbb{P}(t)=0$. Since there is a finite number of non-terminals, there is a finite number of equivalence classes under $\equiv_{H}$.
\end{proof}

To prove Proposition~\ref{prop:SUWCFGhaveCMTA} we 
first show how to convert a WCFG into a PMTA. Then we claim, that in case the WCFG is structurally unambiguous
the resulting PMTA is a CMTA.

\paragraph{Converting a WCFG to a PMTA}
Let $\tuple{\grmr{G},\theta}$ be a WCFG where $\grmr{G}=\langle \ensuremath{\mathcal{V}},\Sigma,R,S\rangle$. Suppose w.l.o.g that $\ensuremath{\mathcal{V}}=\{N_{0},N_{1},...,N_{|\ensuremath{\mathcal{V}}|-1}\}$, $\Sigma=\{\sigma_{0},\sigma_{1},...,\sigma_{|\Sigma|-1}\}$ and that $S=N_{0}$. Let $n=|\ensuremath{\mathcal{V}}|+|\Sigma|$. We define a function $\iota:\ensuremath{\mathcal{V}}\cup\Sigma\rightarrow\mathbb{N}_{\leq n}$ in the following manner:
\[
\iota(x) =
\begin{dcases*}
j
   & $x=N_{j}\in \ensuremath{\mathcal{V}}$\\
   |\ensuremath{\mathcal{V}}|+j
   & $x=\sigma_{j}\in \Sigma$
\end{dcases*}
\]
Note that since $\ensuremath{\mathcal{V}}\cap\Sigma=\emptyset$, $\iota$ is well defined. It is also easy to observe that $\iota$ is a bijection, so $\iota^{-1}:\mathbb{N}_{\leq n}\rightarrow \ensuremath{\mathcal{V}}\cup\Sigma$ is also a function.\\
We define a PMTA $\mathcal{A}_{\mathcal{G}}$ in the following manner:  
\begin{equation*}
    \mathcal{A}_{\mathcal{G}}=(\Sigma,\mathbb{R}_+,n,\mu,\lambda)
\end{equation*}
where
\begin{equation*}
    \lambda=[1,0,...,0]
\end{equation*}
(that is, $\lambda[0]=1$, and for $1<i\leq n$ $\lambda[i]=0$).

For each $\sigma\in\Sigma$ we define
\[
\mu_\sigma[i] =
\begin{dcases*}
1
   & $i=\iota(\sigma)$\\
   0
   & otherwise
\end{dcases*}
\]

For $(i,i_1,i_2,\ldots,i_j)\in \{1,2\ldots,|\ensuremath{\mathcal{V}}|\}^{|j|+1}$,
we define $R^{-1}(i,i_1,i_2,\ldots,i_j)$ to be the production rule
\[ \iota^{-1}(i)\longrightarrow \iota^{-1}(i_{1})~\iota^{-1}(i_{2})~\cdots~\iota^{-1}(i_{j}) \]
We define $\mu_?$ in the following way:
\[
{{\mu_?}^{i}}_{i_{1},...,i_{j}} =
\begin{dcases*}
\theta(R^{-1}(i,i_1,i_2,\ldots,i_j)) & $1\leq i\leq |\ensuremath{\mathcal{V}}|$\\
   0 & otherwise
\end{dcases*}
\]

We claim that the weights computed by the constructed PMTA
agree with the weights computed by the given grammar.

\begin{proposition}\label{prop:equiv2}
For each skeletal tree ${t\in \skels(\deriv(\grmr{G}))}$ we have that $\mathcal{W}_{\mathcal{G}}(t)=\mathcal{A}_{\mathcal{G}}(t)$.
\end{proposition}

\begin{proof}
The proof is reminiscent of the proof in the other direction, namely that of Proposition~\ref{prop:equiv1}.
We  first prove by induction that for each $t\in \skels(\deriv(\grmr{G})))$ the vector $\mu(t)=v=(v[1],v[2],...,v[n])$ calculated by $\mathcal{A}_{\mathcal{G}}$ maintains that for each $i\leq |\ensuremath{\mathcal{V}}|$, $v[i]=\grmrwgt{N_i}{t}$; and for $i>|\ensuremath{\mathcal{V}}|$ we have that $v[i]=1$ iff $t=\iota^{-1}(i)$ and $v[i]=0$ otherwise.

The proof is by induction on the height of $t$. For the base case $h=1$, thus $t$ is a leaf, therefore $t=\sigma\in\Sigma$. By definition $\mu_\sigma[i]=1$ if $i=\iota(\sigma)$ and $0$ otherwise. Hence $v[\iota(\sigma)]=1$, and for every $i\neq\iota(\sigma)$ $v[i]=0$. Since the root of the tree is in $\Sigma$, the root of the tree can't be a non-terminal, so $\grmrwgt{N_i}{t}=0$ for every $i$. Thus, the claim holds. 


For the induction step,  $h>1$, thus $t=(? (t_{1}, t_{2},...,t_{k}))$ for some skeletal trees $t_{1}, t_{2},...,t_{k}$ of depth at most $h$. Let $\mu(t)=v=(v[1],v[2],...,v[n])$ be the vector calculated by $\mathcal{A}$ for $t$. By our definition of $\mu_?$, for every $i>|\ensuremath{\mathcal{V}}|$ ${{\mu_?}^{i}}_{i_{1},...,i_{j}}=0$ for all values of $i_{1},i_{2},...,i_{j}$. So for every $i>|\ensuremath{\mathcal{V}}|$ we have that $v[i]=0$ as required, since $t\notin\Sigma$. Now for $i\leq|\ensuremath{\mathcal{V}}|$. By definition of a multi-linear map we have that:
\begin{equation*}
        v[i]=\sum_{(i_1,i_2,\ldots,i_j)\in [|\ensuremath{\mathcal{V}}|]^j} {{\mu_?}^{i}}_{i_{1},...,i_{j}}\,v_{1}[j_{1}]\cdot...\cdot v_{j}[i_{j}]
\end{equation*}


Since $i\leq |\ensuremath{\mathcal{V}}|$, by our definition we have that:
\begin{equation*}
    {{\mu_?}^{i}}_{i_{1},...,i_{j}}\,=\theta(\iota^{-1}(i)\longrightarrow \iota^{-1}(i_{1})~\iota^{-1}(i_{2})~\cdots~\iota^{-1}(i_{j}))
\end{equation*}
For each $i_{k}$ let $B_{k}=\iota^{-1}(i_{k})$, also since $i\leq |\ensuremath{\mathcal{V}}|$, $\iota^{-1}(i)=N_{i}$, so:
\begin{equation*}
    {{\mu_?}^{i}}_{i_{1},...,i_{j}}\,=\theta(N_{i}\longrightarrow B_{1}B_{2}...B_{j})
\end{equation*}
For each $i$, by our induction hypothesis, if $t_{i}$ is a leaf, $v_{i}[j_{i}]=1$ only for $j_{i}=\iota(t_{i})$, and otherwise $v_{i}[j_{i}]=0$. If $t_{i}$ is not a leaf, then $v_{i}[j_{i}]=0$ for every $j_{i}>|\ensuremath{\mathcal{V}}|$; and for $j_{i}\leq |\ensuremath{\mathcal{V}}|$, we have that $v_{i}[j_{i}]=\grmrwgt{N_{j_i}}{t_i}$. Therefore we have:
\[
        v[i]=\sum_{(i_1,i_2,\ldots,i_j)\in [|\ensuremath{\mathcal{V}}|]^j} \begin{array}{l}
        \theta(N_{i}\rightarrow B_{1}B_{2}...B_{j})\cdot \\
        \grmrwgt{N_{i_1}}{t_1}\cdots \grmrwgt{N_{i_j}}{t_j}
        \end{array}
\]
So by lemma \ref{lem:weight} we have that $v[i]=\grmrwgt{N_{i}}{t}$ as required.

Finally,
since $S=N_{0}$ and since by our claim, for each $i\leq |\ensuremath{\mathcal{V}}|$, $v_{i}=v[i]=\grmrwgt{N_{i}}{t}$, we get that $v[1]=\grmrwgt{S}{t}$. Also, since $\lambda=(1,0,...,0)$ we have that $\mathcal{A}_{\mathcal{G}}(t)$ is $v[1]$, which is $\grmrwgt{S}{t}$. Thus, it follows that  $\mathcal{W}_{\mathcal{G}}(t)=\mathcal{A}_{\mathcal{G}}(t)$
for every $t\in \skels(\deriv(\grmr{G}))$. 
\end{proof}




To show that the resulting PMTA is a CMTA we
need the following lemma.
We recall that a CFG $\grmr{G}=\langle \ensuremath{\mathcal{V}},\Sigma,R,S\rangle$ is said to be
invertible if and only if $A \rightarrow \alpha$ and $B \rightarrow \alpha$ in $R$ implies $A = B$

\begin{lemma}\label{lem:invertible-iff-structuambig}
A CFG is invertible iff it is structurally unambiguous
\end{lemma}
\begin{proof}
Let $\grmr{G}$ be a SUCFG. We  show that $\grmr{G}$ is invertible. Assume towards contradiction that there are derivations $N_{1}\rightarrow\alpha$ and $N_{2}\rightarrow\alpha$. Then the tree $?(\alpha)$ is structurally ambiguous since its root can be tagged by both $N_{1}$ and $N_{2}$.

Let $\grmr{G}$ be an invertible grammar. We  show that $\grmr{G}$ is an SUCFG. Let $t$ be a skeletal tree. We show by induction on the height of $t$ that there is a single tagging for $t$.

For the base case, the height of $t$ is $1$. Therefore, $t$ is a leaf so obviously, it has a single tagging.

For the induction step, we  assume that the claim holds for all skeletal trees of height at most $h\geq 1$. Let $t$ be a tree of height $h+1$. Then $t=?(t_{1},t_{2},...,t_{p})$ for some trees $t_{1},t_{2},...,t_{p}$ of smaller depth. By the induction hypothesis, for each of the trees $t_{1},t_{2},...,t_{p}$ there is a single possible tagging. 
Hence we have established that all nodes of $t$, apart from the root, have a single tagging.
Let $X_{i}\in\Sigma\cup N$ be the only possible tagging for the root of $t_{i}$. Let $\alpha=X_{1}X_{2}...X_{p}$. Since the grammar is invertible, there is a single non-terminal $N$ s.t. $N\rightarrow\alpha$. Hence, there is a single tagging for the root of $t$ as well. Thus $\grmr{G}$ is structurally unambiguous.
\end{proof}

We are finally ready to prove \claimref{Proposition~\ref{prop:SUWCFGhaveCMTA}}:
\begin{itemize}
	\item []
	\emph{A CMTA can represent an SUWCFG.}
\end{itemize}

\begin{proof}
    By Proposition~\ref{prop:equiv2} a WCFG $\tuple{\grmr{G},\theta}$
    can be represented by a PMTA $\aut{A}_{\grmr{G}}$, namely they provide the same weight for every
    skeletal tree. By Lemma~\ref{lem:invertible-iff-structuambig} the fact that $\grmr{G}$ is unambiguous implies
    it is invertible. We show that given $\grmr{G}$ is invertible, the 
    resulting PMTA is actually a CMTA. That is, in every column of the matrices of $\aut{A}_{\grmr{G}}$,
    there is at most one non-zero coefficient. Let $\alpha\in (\Sigma\cup \ensuremath{\mathcal{V}})^{p}$, let $\iota(\alpha)$ be the extension of $\iota$ to $\alpha$ (e.g. $\iota(aN_7bb)=\iota(a)\iota(N_7)\iota(b)\iota(b)$).
    Since $\grmr{G}$ is invertible, there is a single $N_{i}$ from which $\alpha$ can be derived, namely for which
     $\grmrwgt{N_{i}}{t^{N_i}_\alpha}>0$ where $t^{N_i}_\alpha$ is a tree deriving $\alpha$ with $N_i$ in the root.
     If $\alpha\in\Sigma$, i.e. it is a leaf, then we have that $\mu_\sigma[j]=0$ for every $j\neq i$, and $\mu_\sigma[i]>0$. If $\alpha\notin\Sigma$, then we have that ${{\mu_?}^{j}}_{\iota(\alpha)}=0$ for every $j\neq i$, and ${{\mu_?}^{i}}_{\iota(\alpha)}>0$, as required.
\end{proof}


\section{Running example}\label{app:example}
We will now demonstrate a running example of the learning algorithm. 
For the unknown target  consider the series which gives probability $\frac{1}{2}^n$ to
strings of the form $a^nb^n$ for $n\geq 1$ and probability zero to all other strings. 
 This series can be generated by the following SUPCFG $\grmr{G}=\langle \ensuremath{\mathcal{V}},\{a,b\},R,S\rangle$
 with $\ensuremath{\mathcal{V}}=\{S,S_{2}\}$, and the following derivation rules:
$$\begin{array}{l@{\ \ \longrightarrow\ \ }lll}
S& aS_{2}~[\frac{1}{2}]\ \mid\ ab~[\frac{1}{2}]\\
S_{2}& Sb~~~[1]
\end{array}$$

The algorithm initializes $T=\{a,b\}$ and $C=\{\diamond\}$, fills in the entries of $M$ using $\query{smq}$s, first for the rows of $T$ and then for their one letter extensions $\Sigma(T)$ (marked in blue), resulting   in the following observation table.
\begin{center}
	\begin{tabular}{ l | l}
		& \Tree [.$\diamond$ ] \\ \hline
		$a$& $0$\\ \hline
		$b$& $0$\\ \hline
		\color{blue} $?(a,a)$ & $0$\\\hline
		\color{blue} $?(a,b)$ & $0.5$\\\hline
		\color{blue} $?(b,a)$ & $0$\\\hline
		\color{blue} $?(b,b)$ & $0$\\\hline
	\end{tabular}
\end{center}

We can see that the table is not closed, since $?(a,b)\in\Sigma(T)$ but is not co-linearly spanned by $T$, so we add it to $T$. Also, the table is not consistent, since $a\treesColin{1}{H} b$, but $\query{mq}(\contextConcat{\diamond}{?(a,b)})\neq\query{mq}(\contextConcat{\diamond}{?(a,a)})$, so we add $?(a,\diamond)$ to $C$, and we obtain the following table.
From now on we  omit $0$ rows of $\Sigma(T)$ for brevity.
\begin{center}
	\begin{tabular}{l | l | l | l }
		& & \Tree [.$\diamond$ ] & $?(a,\diamond)$ \\ \hline
		$t_1$ & $a$ & $0$ & $0$ \\ \hline
		$t_2$ & $b$ & $0$ & $0.5$\\ \hline
		$t_3$ & $?(a,b)$ & $0.5$ &$ 0$ \\\hline
		& \color{blue} $?(?(a,b),b)$ & $0$ & $0.25$ \\
	\end{tabular}
\end{center}
The table is now closed but it is not zero-consistent, since we have $H[a]=\overline{0}$, but there exists a context with children in $T$, specifically $?(\diamond,b)$,
with which when $a$ is extended the result is not zero, namely $H[?(a,b)]\neq 0$. So we add this context
and we obtain the following table:

\vspace{2mm} 
\begin{center}
	\begin{tabular}{l | l | l | l | l }
		& & \Tree [.$\diamond$ ] & $?(a,\diamond)$ & $?(\diamond,b)$\\ \hline
		$t_1$ & $a$ & $0$ & $0$ & $0.5$ \\ \hline
		$t_2$ & $b$ & $0$ & $0.5$ & $0$ \\ \hline
		$t_3$ & $?(a,b)$ & $0.5$ & $0$ \\\hline
		$t_4\notin B$ & $?(a,a)$ & $0$ & $0$ & $0$ \\\hline
		& \color{blue} $?(?(a,b),b)$ & $0$ & $0.25$ & $0$ \\
	\end{tabular}
\end{center}
\vspace{2mm} 

Note that $t_{4}$ was added to $T$ since it wasn't spanned by $T$, but it is not a member of $B$, since $H[t_{4}]=0$. 
We can extract the following CMTA $\aut{A}_1=(\Sigma,\mathbb{R},d,\mu,\lambda)$ of dimension $d=3$ since $|B|=|\{t_{1},t_{2},t_{3}\}|=3$.
Let $\mathbb{V}=\mathbb{R}^3$.  For the letters $\sigma\in \Sigma_0=\{a,b\}$ we have that $\mu_\sigma:\mathbb{V}^0\rightarrow \mathbb{V}$, namely $\mu_a$ and $\mu_b$ are $3\times 3^0$-matrices. Specifically, following Alg.~5 we get that $\mu_{a}=(1,0,0)$, $\mu_{b}=(0,1,0)$ as $a$ is the first element of $B$ and $b$ is the second.
For ${?}\in\Sigma^2$ we have that $\mu_{?}:\mathbb{V}^2\rightarrow \mathbb{V}$, thus $\mu_{?}$ is a $3\times 3^2$-matrix.
We compute the entries of $\mu_{?}$ following Alg.~5. For this, we consider all pairs of indices $(j,k)\in\{1,2,3\}^2$. For each such entry we look for the row $t_{j,k}=?(t_j,t_k)$
and search for the base row $t_i$ and the scalar $\alpha$ for which  $t_{j,k} \treesColin{\alpha}{H} t_i$.
We get that $t_{1,2}\treesColin{1}{H} t_3$, $t_{3,2}\treesColin{0.5}{H} t_2$ and for all other $j,k$ we get $t_{j,k}\treesColin{1}{H} t_{4}$, so we set $c^{i}_{j,k}$ to be $0$ for every $i$. Thus, we obtain the following matrix for $\mu_{?}$
$$
\eta_{?}=\begin{bmatrix}0&0&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&0.5&0\\
0&1&0&0&0&0&0&0&0\end{bmatrix}$$
 The vector $\lambda$ is also computed via Alg.~5, and we get $\lambda=(0,0,0.5)$. 
 
 The algorithm now asks an equivalence query and receives the following tree as a counter-example:
 
 $p=$\Tree [.? $a$ [.? [.? $a$ $b$ ] [.? [.? $a$ $b$ ] $b$ ] ] ]
 
 Indeed, while $\query{smq}(p)=0$ we have that $\aut{A}(p)=0.125$. To see why $\aut{A}(p)=0.125$, let's look at the values $\mu(t)$ for every sub-tree $t$ of $p$. For the leaves, we have $\mu(a)=(1,0,0)$ and $\mu(b)=(0,1,0)$.
 
 Now, to calculate $\mu(?(a,b))$, we need to calculate $\mu_{?}(\mu(a),\mu(b))$. To do that, we first compose them as explained in the \emph{Multilinear functions} paragraph of Sec.~\ref{sec:mta}, see also Fig.~\ref{fig:MTA}. The vector $P_{\mu(a),\mu(b)}$ is: $P_{\mu(a),\mu(b)}=(0,1,0,0,0,0,0,0,0)$. When multiplying this vector by the matrix $\eta_{?}$ we obtain $(0,0,1)$. So $\mu(?(a,b))=(0,0,1)$. Similarly, to obtain  $\mu(?(?(a,b),a))$ we first compose the value $(0,0,1)$
 for $?(a,b)$ with the value $(0,1,0)$ for $a$ and obtain $P_{\mu?(a,b),\mu(a)}=(0,0,0,0,0,0,0,1,0)$. 
 Then we multiply $\eta_{?}$ by $P_{\mu?(a,b),\mu(a)}$ and obtain $(0,0.5,0)$. In other words, 
 $$\mu(?(?(a,b),a))=\mu_{?}(\begin{bmatrix}0\\ 0\\ 1\end{bmatrix},\begin{bmatrix}0\\ 1\\ 0\end{bmatrix})=\begin{bmatrix}0\\0.5\\0\end{bmatrix}.$$ 
 
 The following tree depicts the entire calculation by marking the values obtained for each sub-tree. We can see that  $\mu(p)=(0,0,0.25)$, thus we get that $\aut{A}=\mu(p)\cdot\lambda=0.125$.
 
\vspace{2mm} 
 \scalebox{.9}{
   \Tree [.$(0,0,0.25)$ $(1,0,0)$ [.$(0,0.25,0)$ [.$(0,0,1)$ $(1,0,0)$ $(0,1,0)$ ] [.$(0,0.5,0)$ [.$(0,0,1)$ $(1,0,0)$ $(0,1,0)$ ] $(0,1,0)$ ] ] ]
}
\vspace{2mm} 

 We add all prefixes of this counter-example to $T$ and we obtain the following table:
 \begin{center}
 	\begin{tabular}{l | l | l | l | l }
 		 & & \Tree [.$\diamond$ ] & \rotatebox[origin=c]{90}{$?(a,\diamond)$} & \rotatebox[origin=c]{90}{$?(\diamond, b)$} \\ \hline
 		$t_1$ & $a$  & $0$ & $0$ & $\frac{1}{2}$ \\ \hline
 		$t_2$ & $b$ & $0$ & $\frac{1}{2}$ &$0$ \\ \hline
 		$t_3$ & $?(a,b)$ & $\frac{1}{2}$ & $0$ & $0$ \\\hline
 		$t_4$ & $?(a,a)$ & $0$ & $0$ & $0$\\\hline
 		$t_5$ & $?(?(a,a),a)$ & $0$ & $0$ & $0$\\\hline
 		$t_6$ & $?(?(a,b),b)$ & $0$ & $\frac{1}{4}$ & $0$ \\\hline
 		$t_7$ & $?(?(a,b),?(?(a,b),b))$ & $0$ & $0$ & $0$\\\hline
 		$t_8$ & $?(a,?(?(a,b),?(?(a,b),b)))$ & $0$ & $0$ & $0$ \\
 	\end{tabular}
 \end{center}
 This table is not consistent since while $t_6 \treesColin{0.5}{H} t_2$ this co-linearity is not preserved when extended with $t_{3}=?(a,b)$ to the left, as evident from the context $?(a,\diamond)$.
We thus add the context $\contextConcat{?(a,\diamond)}{?(?(a,b),\diamond)}=?(a,?(?(a,b),\diamond))$ to obtain the final table:

 \begin{center}
 	\begin{tabular}{l | l | l | l | l | l}
 		& & \Tree [.$\diamond$ ] & \rotatebox[origin=c]{90}{$?(a,\diamond)$} & \rotatebox[origin=c]{90}{$?(\diamond, b)$} & \rotatebox[origin=c]{90}{$?(a,?(?(a,b),\diamond))$}\\ \hline
 		$t_1$ & $a$ & $0$ & $0$ & $\frac{1}{2}$ & $0$\\ \hline
 		$t_2$ & $b$ & $0$ & $\frac{1}{2}$ & $0$ & $\frac{1}{4}$ \\ \hline
 		$t_3$ & $?(a,b)$ & $\frac{1}{2}$& $0$ & $0$ & $0$ \\\hline
 		$t_4$ & $?(a,a)$ & $0$ & $0$ & $0$ & $0$ \\\hline
 		  & $?(?(a,a),a)$ & $0$ & $0$ & $0$ & $0$ \\\hline
 		$t_5$ & $?(?(a,b),b)$ & $0$ & $\frac{1}{4}$ & $0$ & $0$ \\\hline
 		  & $?(?(a,b),?(?(a,b),b))$ & $0$ & $0$ & $0$ & $0$\\\hline
 		  & $?(a,?(?(a,b),?(?(a,b),b)))$ & $0$ & $0$ & $0$ & $0$ \\\hline
 		 $t_6$  & \color{blue}$?(a,?(?(a,b),b))$ & $\frac{1}{4}$  & $0$ & $0$ & $0$ \\
 	\end{tabular}
 \end{center}
 The table is now closed and consistent, and we extract the following CMTA from it: 
 $\aut{A}_3=(\Sigma,\mathbb{R},4,\mu,\lambda)$ with $\mu_{a}=(1,0,0,0)$, $\mu_{b}=(0,1,0,0)$. 
 Now $\mu_{?}$ is a $4\times 4^2$ matrix. Its interesting entries are $c^3_{1,2}=1$, $c^4_{3,2}=1$ and $c^3_{1,4}=\frac{1}{2}$
 since $t_{1,2}\treesColin{1}{H} t_3$, $t_{3,2} \treesColin{1}{H} t_5$, $t_{1,5} \treesColin{1}{H} t_6 \treesColin{0.5}{H} t_3$.
 And  for every other combination of unit-basis vectors we have $t_{i,j}\treesColin{1}{H} t_4$.   
 The final output vector is $\lambda=(0,0,0.5,0)$.
 
 The equivalence query on this CMTA returns true, hence the algorithm now terminates, and we can convert this CMTA into a WCFG. 
 Applying the transformation provided in Fig.~\ref{fig:eqs-pmta-to-pcfg} we obtain the following WCFG:
 \begin{align*}
 S&\longrightarrow N_{3}~[0.5]   \\
 N_{1}&\longrightarrow a~[1.0 ]  \\
 N_{2}&\longrightarrow b~[1.0]   \\
 N_{3}&\longrightarrow N_{1} N_{2}~[1.0]\ \  |\ \ N_{1} N_{4}~[0.5]   \\
 N_{4}&\longrightarrow N_{3} N_{2}~[1.0]  
 \end{align*}
 
 Now, following~\cite{abney1999relating,smith2007weighted}
 we can calculate the partitions functions for each non-terminal. Let $f_{N}$ be the sum of the weights of all trees whose root is $N$, we obtain:
 \begin{align*}
 f_{S}&=1\\
 f_{N_{1}}&=1\\
 f_{N_{2}}&=1\\
 f_{N_{3}}&=2\\
 f_{N_{4}}&=2\\
 \end{align*}
 
 Hence we obtain the PCFG 
 \begin{align*}
 S&\longrightarrow N_{3}~[1.0]\\
 N_{1}&\longrightarrow a~[1.0]\\
 N_{2}&\longrightarrow b~[1.0]\\
 N_{3}&\longrightarrow N_{1} N_{2}~[0.5]\ |\ N_{1} N_{4}~[0.5]\\
 N_{4}&\longrightarrow N_{3} N_{2}~[1.0]
 \end{align*}
 which is a correct grammar for the unknown probabilistic series.
 
