Изменения

Алгоритм является универсальным для всех КС-грамматик, которые должны быть приведены в нормальную форму Хомского без &epsilon;-правил. Правила такой грамматики имеют вид либо А&rarr;а, либо А&rarr;BC, где a - терминал, B и C нетерминалы ,не являющиеся начальными. Алгоритм имеет сложность <mathtex>O(n^3)</mathtex> и использует <mathtex>O(n^2)</mathtex> памяти.

Сам алгоритм состоит в построении треугольной матрицы разбора T по заданной входной строке '''<mathtex>a_1, a_2, \ldots, a_n</mathtex>'''. В каждый элемент этой матрицы <mathtex>t_{ik}</mathtex> помещаются все нетерминалы, из которых можно вывести отрезок входной строки длины k, начинающийся i-ым символом: '''<mathtex>a_i, \ldots, a_{i+k-1}</mathtex>'''.

:: '''<mathtex>\forall</mathtex>i <mathtex>t_{i1}</mathtex> = { A | A &rarr; <mathtex>a_i</mathtex>};''':: '''<mathtex>\forall</mathtex>i < j <mathtex>t_{ij}</mathtex> = {A | A&rarr;BC и <mathtex>1 \leqslant k < j : B \in t_{ik}, C \in t_{i+k, j-k}</mathtex>}.'''Действительно, в каждый элемент <mathtex>t_{i1}</mathtex> (в данном случае удобнее рассматривать первой нижнюю строку) помещаются все нетерминалы, для которых существует правило A &rarr; <mathtex>a_i</mathtex>. Пусть теперь заполнены все строки до j-1-й включительно. Рассмотрим элемент <mathtex>t_{ij}</mathtex>, соответствующий фрагменту &lt;<<mathtex>a_1,\ldots, a_j </math>tex> &gt; входной строки. Разобьём его всеми способами на пары соседних строк '''<mathtex><a_i> и <a_{i+1}...a_j>; <a_ia_{i+1}> и <a_{i+2} ...a_j></mathtex>''', и т.д. Каждому варианту разбиения соответствует пара элементов матрицы, в которых стоят нетерминалы, из которых могут быть выведены соответствующие строки. Пусть эта пара элементов – (t',t"). В рассматриваемый элемент <mathtex>t_{ij}</mathtex> помещаем нетерминал А, если среди правил грамматики есть правило А&rarr;ВС, и нетерминал В входит в элемент t', а С – входит в элемент t".

Входная строка принадлежит языку, порождаемому грамматикой, если в элементе <mathtex>t_{1n}</mathtex> встретится начальный нетерминал.