[[Файл:table.jpg|300px|thumb|right|Таблица разбора алгоритма для цепочки из шести символов. В клетку <tex>t_{34}</tex> должны быть помещены нетерминалы, из которых выводится фрагмент входной строки длиной четыре символа, начинающийся с <tex>a_{3}</tex>, т.е. это цепочка <tex>a_{3}a_{4}a_{5}a_{6}</tex>. Этот фрагмент тремя способами можно разбить на пары непустых соседних фрагментов: (1) <tex>a_{3}</tex> и <tex>a_{4}a_{5}a_{6}</tex>, (2): <tex>a_{3}a_{4}</tex> и <tex>a_{5}a_{6}</tex>, (3): <tex>a_{3}a_{4}a_{5}</tex> и <tex>a_{6}</tex>. Этим трем парам фрагментов соответствуют пары клеток, в которых могут стоять нетерминалы, из которых эти фрагменты выводятся: (1) <tex>t_{31}</tex> и <tex>t_{43}</tex>, (2): <tex>t_{32}</tex> и <tex>t_{52}</tex>, (3): <tex>t_{33}</tex> и <tex>t_{61}</tex>. Если в этих клетках находятся соответственно нетерминалы B и C и существует правило A→BC, то A заносится в <tex>t_{34}</tex>]]
= Формальная грамматика =
Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением задачи динамического программирования на подотрезке.
=== Псевдокод ===
<tex>a_1...a_n</tex> - входная строка. <tex>A_1...A_m</tex> - нетерминалы.
<tex>P[i,j,k] = true</tex> если есть продукция <tex>A_i \Rightarrow A_j A_k</tex>.
<tex>S(i,c) = true</tex> если есть продукция <tex>A_i \Rightarrow c</tex> (где <tex>c</tex> - терминал).
<tex>d[i][j,k]</tex> - можно ли вывести из нетерминала <tex>A_i</tex> подстроку <tex>a_j...a_k</tex>.
for i = 1 to m
for j = 1 to n
d[i][j,j] = S(i,a[j])
// дописать
= Ссылки =
