53
правки
Изменения
→Алгоритм для произвольной грамматики
* '''База динамики''': <tex>a_{A, i, i} = \left[ A \rightarrow w[i] \in P \right]</tex> — вывод терминалов, <tex>\forall i \:\: a_{A, i, i-1} = \left[ A \rightarrow \varepsilon \right]</tex> — <tex>\varepsilon</tex>-вывод, <tex>\forall i,A \rightarrow \alpha \:\: h_{A \rightarrow \alpha, i, i-1, 0} = true</tex> — <tex>\varepsilon</tex>-вывод для <tex>\varepsilon</tex>-префиксов.
* '''Переход''': Пусть для всех подстрок <tex>w[i..j]</tex> динамики уже вычислены. Сначала вычислим вспомогательную динамику: <tex>\forall k: h_{A \rightarrow \alpha, i, j, k} = \bigvee\limits_{r=i-1..j}\left(h_{A \rightarrow \alpha, i, r, k-1} \wedge a_{\alpha_k,r+1,j}\right)</tex>. Это вычисление может обратится к <tex>a_{A,i,j}</tex>, но на результат это не повлияет, так так в данный момент <tex>a_{A,i,j}=false</tex>. Главная динамика выражается так: <tex>a_{A,i,j}=\bigvee\limits_{A \rightarrow \alpha}h_{A \rightarrow \alpha, i, j, \left|\alpha\right|}</tex>.
* '''Завершение''': После окончания работы ответ содержится в ячейке <tex>a_{S, 1, n}</tex>, где <tex>n = |w|</tex>.
