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