In the worst case, the fan-out of p 2 can be as large as ϕ(B r−1 ) + ϕ(B r ).
1: Function NAIVE-BINARIZATION(p) 2: result ← ∅; 3: currentProd ← p; 4: while ρ(currentProd) > 2 do 5: currentProd ← p 1 ; 8: return result ∪ currentProd; We have defined reductions only for the last two occurrences of nonterminals in the right-hand side of a production p. it is easy to see that we can also define the concept for two arbitrary (not necessarily adjacent) occurrences of nonterminals, at the cost of making the notation more complicated.