70
правок
Изменения
Нет описания правки
<tex>I_j' = I_j''</tex>
<tex>I_j'' = \varnothing</tex>
for <tex>[B \rightarrow \eta \cdot , i] \in I_j'</tex># (*)
for <tex>[A \rightarrow \alpha \cdot B \beta, k] \in I_{i}</tex>
<tex>I_j''</tex> ∪= <tex>[A \rightarrow \alpha B \cdot \beta, k]</tex> # Правило (2)
for <tex>[B \rightarrow \alpha \cdot A \eta, k] \in I_j'</tex># (**)
for <tex>\beta : (A \rightarrow \beta) \in P</tex>
<tex>I_j''</tex> ∪= <tex>[A \rightarrow \cdot \beta, j]</tex> # Правило (3)
<tex>I_j</tex> ∪= <tex>I_j''</tex>
В циклах, помеченных <tex>(*)</tex> и <tex>(**)</tex> просматривается не весь список <tex>I_j</tex>, а только те ситуации, которые еще не были просмотрены. Данная модификация является корректной.
# Рассмотрим цикл <tex>(*)</tex>. Если в текущей ситуации <tex>[B \rightarrow \eta \cdot, i]</tex> этого цикла <tex>i \ne j</tex>, то во внутреннем цикле просматривается список с меньшим индексом, в который новые ситуации больше не добавляются. Поэтому после первого просмотра этого списка будут добавлены все ситуации, удовлетворяющие условию, и больше ситуацию <tex>[B \rightarrow \eta \cdot, i]</tex> в цикле <tex>(*)</tex> рассматривать не нужно. Если же <tex>i = j</tex>, то <tex>\eta \Rightarrow^* \varepsilon</tex>, что возможно, только если <tex>B = S \, , \eta = \varepsilon</tex>. Тогда во внутреннем цикле не будет добавлено ни одной ситуации, так как <tex>S</tex> не встречается в правых частях правил.
# Теперь рассмотрим цикл <tex>(**)</tex>.
==Время работы для однозначной грамматики==
{{Лемма
