Proof Any segmentation of the sentence of length M starts with either a segment of length 1, a segment of length 2, • • • , or a segment of length L. Thus, g(M ; L) can be defined through the following recurrence relation: together with the initial values g(1; L), g(2; L), • • • , g(L; L), which can be computed offline (for example, for L = 3, one has: g(1; 3) = 1, g(2; 3) = 2, g(3; 3) = 4).
note that g(1; L) = 1 for all L. : due to the recurrence relation on g. This proves the first part of the proposition.