Решение

Таблица разбора для данной цепочки строится следующим образом. Выполняем шаг 1 алгоритма, т.е. определяем элементы :

.

Таблица разбора будет выглядеть следующим образом

`5

Выполняем шаг 2 при .

Для получаем

,

т.к.

.

Для получаем

,

т.к.

.

Для получаем

,

т.к.

.

Для получаем

,

т.к.

.

Таблица разбора будет выглядеть следующим образом

`5

Выполняем шаг 2 при .

Для получаем

,

т.к.

.

Для получаем

,

т.к.

.

Для получаем

,

т.к.

.

Таблица разбора будет выглядеть следующим образом

`5

Выполняем шаг 2 при .

Для получаем

,

т.к.

.

Для получаем

,

т.к.

.

Таблица разбора будет выглядеть следующим образом

`5

Выполняем шаг 2 при .

Для получаем

,

т.к.

.

Таблица разбора будет выглядеть следующим образом

`5

Делаем проверку на принадлежность входной цепочки заданному языку. Так как , то .

Алгоритм нахождения левого разбора по таблице разбора

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

2. Таблица разбора , построенная для цепочки .

Выход: Левый разбор цепочки или сигнал – «ошибка».

Метод:

Опишем рекурсивную процедуру , порождающую левый разбор, соответствующий выводу .

1. Делаем проверку: если , то и переходим к шагу 2, в противном случае, если , выдаем сигнал – «ошибка».

2. Вызываем процедуры . перед вызовом процедуры положим .

3. Если и правило имеет номер , то .

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

Пример №1

Задание.

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

и пусть - входная цепочка. Также задана таблица разбора вида

`5

Дата добавления: 2014-01-07