Алгоритм разбора Кока-Янгера-Касами

Вход: КС-грамматика в нормальной форме Хомского без пустых правил (ВСЕХ!!!) и входная цепочка .

Выход: Таблица разбора для цепочки , такая, что. тогда и только тогда, когда

Метод:

1. Положить . Очевидно, что .

2. Допустим, что уже вычислены . Тогда

Так как , то и . Таким образом, и вычисляются раньше, чем . После этого из следует, что

3. Повторяем шаг 3 до тех пор, пока не станут известны .

Пример №1

Задание.

Пусть задана грамматика в нормальной форме Хомского с правилами

и пусть - входная цепочка.

Дата добавления: 2014-01-07; Просмотров: 2231; Нарушение авторских прав?; Мы поможем в написании вашей работы!