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