Since T has m constituents, by induction hypothesis, T is a reachable set from configuration c. Since (X, l, r) is individually reachable by hypothesis, it must satisfy at least one of the conditions for constituent reachability.
as these conditions are different for each particular algorithm, we continue the proof separately for each: Top-down constituent-decomposability In this case, we enumerated three constituent reachability conditions, so we divide the proof into three cases: If the first condition holds, then the constituent (X, l, r) has already been created in c. it will still be present after applying any of the possible transition sequences that build T starting from c. Hence, T = T ∪ {(X, l, r)} is reachable from c. If the second condition holds, then j ≤ l < r and the constituent (X, l, r) can be created by l−j Shift transitions, followed by one Non-Terminal transition, r − l Shift transitions and one Reduce transition.