## 2 Formal Definitions
Checking the grammar more closely we find two points where the length of the word generated from an intermediate symbol is not determined when the symbol is introduced during a derivation: At the start of the derivation the length of the generated word is not predetermined and when the rule \(S\rightarrow\mathcal{A}\mathcal{A}\) is applied to generate a word of length \(l\) there are _l_\(+1\) possible ways how the length can be distributed amongst the two symbols \(\mathcal{A}\). Both cases can be countered by adding the proper probability distributions to the model. However while the start needs a single probability distribution \(\mathcal{P}_{\ell}\) on the natural numbers (or a subset of them, if the grammar can not generate words of arbitrary length), the distribution of the lengths amongst the right side of the rule requires for each length \(l\) a set of _l_\(+1\) probabilities (generally \(\mathcal{O}(\mathit{\cdot}^{-1})\) for a rule with \(l\) intermediate symbols on the right-hand side). Obviously storing these values with the grammar explicitly is not feasible unless we only want to consider short words. Approximating them with easily describable functions seems possible, but would potentially be difficult to automate and would not be covered by the considerations in Section 3. Thus we decided to use uniform distributions here. Combining the above considerations length-dependent stochastic context-free grammars can be defined:  
**Definition 3**. : _A length-dependent stochastic context-free grammar (LSCFG) is a 6-tuple \(G=(1\!:\!T\!:\!R\!:\!S\!:\!P\! :\!P_{\ell})\), where \((1\!:\!T\!:\!R\! :\!S)\) is a CFG, \(P\!:\!R\times\mathbb{N}\rightarrow[0\! :\!1]\) is a mapping such that each pair of a rule \(r\in R\) and a length \(l\in\mathbb{N}\) is equipped with a probability \(P(r\! :\!l)\) satisfying \(\forall A\in\,l\,\forall l\in\mathbb{N}:\sum_{A\rightarrow\alpha\in R}P(A \rightarrow\ \ \ \!:\!l)\in\{0\! :\!1\}\) and \(P_{\ell}:\mathbb{N}\rightarrow[0\! :\!1]\) assigns probabilities to the lengths of words in \(L(G)\) such that \(\sum_{\genfrac{}{}{0.0 pt}{}{n\in\mathbb{N}}{T^{n}\cap L(G)\
eq\emptyset}}P_{ \ell}(\eta)=1\)._  
_For \(A\rightarrow\ \ \in R\) and \(l\in\mathbb{N}\) we define \(\rho_{\alpha,l}=\frac{1}{c_{\alpha,l}}\), where \(c_{\alpha,l}\) is the number of different assignments of lengths to the symbols of  that satisfy:_  
* _Terminals are always assigned a length of_ \(1\)_._
* _Any intermediate symbol_ \(B\) _is assigned a length_ \(l\) _for which_ \(\exists w\in\,T^{i}:P(B\Rightarrow^{*}w)\,>0\)_._
* _The assigned lengths add up to_ \(l\)_._  
_Words are generated as for usual context-free grammars. The probability \(P(\Delta)\) of a parse tree \(\Delta\) is then the product of the probabilities of all rule applications in \(\Delta\), each multiplied by \(\rho_{\alpha,l}\), where \(\\) is the right hand side, \(l\) is the length of the respective rule application. The sum of the probabilities of all possible parse trees of a derivation \(A\Rightarrow^{*}\\) provides the probability \(P(A\Rightarrow^{*}\\)). Finally for a word \(w\in L(G)\) its probability is given by \(P(w)=P_{\ell}(|w|)\cdot P(S\Rightarrow^{*}w)\)._  
\(G\) _is called consistent iff \(\sum_{w\in L(G)}P(w)=1\), i.e., it defines a probability distribution on \(L(G)\)._  
This definition allows for the productions to be equipped with arbitrary probabilities as long as for any given pair (premise, length) they represent a probability distribution or are all \(0\). In the present paper we will however confine ourselves with grouping the lengths together in finitely many intervals, a rule having the same probability for lengths that are in the same interval. This allows for the probabilities to be stored as a vector and be retrieved in the algorithms without further computation. It is however, as we will see, still powerful enough to yield a significant improvement over non-length-dependent SCFGs with respect to the quality of the prediction. **Note 1**.