Given these added complications one might consider simply eliminating all -productions in a preprocessing step. This is mostly straightforward and analogous to the corresponding procedure for non-probabilistic CFGs [Aho and Ullman1972, Algorithm 2.10,]. The main difference is the updating of rule probabilities, for which the -expansion probabilities are again needed.
The crucial step in this procedure is the addition of variants of the original productions that simulate the null productions by deleting the corresponding nonterminals from the RHS. The spontaneous dot shifting described in the previous sections effectively performs the same operation on the fly as the rules are used in prediction and completion.