Разложимые системы продукций

Рассмотрим в качестве примера следующую систему продукций:

начальная г.б.д. (C,B,Z);

правила переписывания (продукции):

R1: C → (D, L);

R2: C → (B, M);

R3: B → (M, M);

R4: Z → (B, B, M);

терминальное условие (M, M... M) (глобальная база данных должна содержать только символы М).

Дадим теперь определение разложимой системы продукций.

Опр. 1. Системы продукций, глобальные базы данных и терминальные условия которых допускают декомпозицию, называются разложимыми.

Система продукций описывает некоторую задачу.

Как понять, что задача допускает декомпозицию?

Если задачу можно разбить на подзадачи, которые можно решать независимо друг от друга, то исходная г.б.д. может быть разбита на отдельные компоненты, обрабатываемые независимо и даже параллельно, и целевое условие для всей г.б.д. можно разложить на конъюнкцию условий для каждой составляющей.

Глобальная база данных из нашего примера является разложимой и разлагается на независимые компоненты C, B, Z. Как мы это установили?

Во-первых, каждое правило продукции использует для проверки предварительного условия только одну компоненту г.б.д. и изменяет только одну компоненту.

Во-вторых, целевое условие раскладывается в конъюнкцию символов (М).

Опр. 2. Представлением задачи, описывающейся разложимой системой продукции, является И-ИЛИ граф.

И-ИЛИ граф является обобщением пространства состояний. Рассмотрим его составляющие.

Вершины И-ИЛИ графа соответствуют задачам; связи между ними — отношениям между задачами и подзадачами.

Вершина типа «ИЛИ»: для решения этой задачи достаточно решить только одну из ее подзадач-преемников (рис. 13):

Рисунок 13. Вершина типа «ИЛИ»

Вершина типа «И»: для решения этой задачи нужно решить все ее подзадачи — преемники (рис. 14):

Рисунок 14. Вершина типа «И»

Целевая вершина: задача, решаемая непосредственно, или г.б.д., удовлетворяющая целевому условию.

Решение задачи: решающее дерево, являющееся подграфом И-ИЛИ графа и связывающее исходную вершину с некоторым подмножеством терминальных.

Заметим, что для пространства состояний решением задачи является путь, связывающий начальную вершину с одной из терминальных, для разложенной системы продукций — решающее дерево.