275
правок
Изменения
м
→Приведение грамматики к нормальной форме Хомского
Заметим, что размеры грамматики при таком порядке действий возрастают полиномиально.
При удалении длинных правил из каждого правила длины <tex> k \ge geqslant 3 </tex> могло появиться <tex> k-1 </tex> новых правил, причем их длина не превышает двух. На этом шаге размер грамматики возрастает не более, чем вдвое.
При удалении <tex> \varepsilon </tex>-правил из грамматики, содержащей правила длины 0, 1 и 2, размеры грамматики могли вырасти не больше, чем в 3 раза.
