<tex>\forall\,j: 1 \le j \le n</tex> в списке <tex>I_j</tex> находится <tex>O(j)</tex> ситуаций.
|proof=
Рассмотрим ситуацию Так как грамматика фиксирована, то <tex>\forall i</tex> количество ситуаций вида <tex>[A \rightarrow \alpha \cdot \beta, i]</tex>не больше константного. Так как количество правилТаким образом, а так же размер их правых частей фиксированыкак в <tex>I_j</tex> находятся ситуации, и у которых <tex>0 \le i \le j</tex>, то всего в <tex>I_j</tex> находится будет <tex>O(j)</tex> ситуаций.
}}
{{Лемма
|about=2
