As an example, consider the following simple left-recursive SCFG.
where q = 1 - p. Non-probabilistically, the prediction loop at position 0 would stop after producing the states
This would leave the forward probabilities at
corresponding to just two out of an infinity of possible paths. The correct forward probabilities are obtained as a sum of infinitely many terms, accounting for all possible paths of length 1.
In these sums each p corresponds to a choice of the first production, each q to a choice of the second production. If we didn't care about finite computation the resulting geometric series could be computed by letting the prediction loop (and hence the summation) continue indefinitely.
Fortunately, all repeated prediction steps, including those due to left-recursion in the productions, can be collapsed into a single, modified prediction step, and the corresponding sums computed in closed form. For this purpose we need a probabilistic version of the well-known parsing concept of a left corner, which is also at the heart of the prefix probability algorithm of Jelinek:91.
The recurrence for 
can be conveniently written in matrix notation
from which the closed-form solution is derived:
An existence proof for is given in
Appendix A.
Appendix B.3.1 shows how to speed up the
computation of by inverting only a reduced version of the
matrix 
.
The significance of the matrix for the Earley algorithm is that
its elements are the sums of the probabilities of the potentially infinitely
many prediction paths leading from a state
to a predicted state
, via any number of intermediate states.
can be computed once for each grammar, and used for table-lookup
in the following, modified prediction step.