Язык управления применением продукций

⇐ ПредыдущаяСтр 20 из 32Следующая ⇒

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

По способу задания можно выделить встроенный и настраиваемый порядки применения продукций. К встроенным относятся средства, которые непосредственно запрограммированы в интерпретаторе системы. Примером встроенного порядка применения правил может служить схема выбора правил в нормальных алгоритмах Маркова. На каждом шаге вывода проверяются условия только одного правила (на первом шаге — первого), если оно не применимо, то происходит переход к следующему. Если оно применилось, то на следующем шаге снова проверяются условия первого правила и т.д. В системе продукции можно упорядочивать по частоте использования или по самым длинным спискам условий, по приоритету и т.п. Кроме этого, в различных системах широко использовалось введение меток и тегов, специальных логических символов внутри продукции для задания последовательности выбора. Такие средства управления порядком применения продукций активно использовались в начальный период конструирования СП, когда под каждую процедуру разрешения конфликта программировался свой интерпретатор. Позднее эти средства подверглись острой критике многими авторами, поскольку их введение означало отход от идеологии СП к традиционным средствам программирования. Это послужило толчком к развитию настраиваемых средств управления.

Первой попыткой в этом направлении было использование в системе HEARSAY-II разбиения правил на подсистемы таким образом, чтобы в каждый момент времени рассматривалось лишь их приемлемое число [90]. Другим средством задания порядка являются метапродукции, использованные в комплексе систем MYCIN-TEIRESIAS [84]. Однако последовательность управляющей информации невозможно описать одними метапродукциями (необходимо введение метаметапродукций и т.д.). По существу, идея введения метапродукций состоит в попытке задать всю возможную информацию в системе однородным образом.

Еще одним средством управления порядком применения правил является использование языков управления. Опишем неформально управляющие формулы и их использование при выводе.

Пусть Рr = {< q_i r_i > }, i = 1... n, п ³ 0 — множество продукций, d — текущее состояние базы данных. На языке управления порядком задается управляющая формула, описывающая множество продукций, для которых на текущем шаге вывода t проверяются условия применимости. Такие множества будем называть множествами активированных продукций a_r, a_r Í Рr.

Каждая продукция рr =< q, r > в задаваемом множестве может быть в одном из трех состояний:

- рr+ — условие продукции рr, активированной на шаге вывода t, должно быть истинно после проверки, т.е. найдется подстановка q такая, что qq Í d;

- рr- — условие продукции рr, активированной на шаге вывода t, должно быть ложно после проверки, т.е. не существует подстановки q такой, что qq Í d;

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

Если, например, А_r = , то переход к A_r₊₁ произойдет в том случае, если условия рr₂ истинны, а рr₃ ложны. Истинность условий pr_i не влияет на переход к A_r₊₁. Требование ложности условий рr₁ является одним из средств задания отрицательного контекста, если он необходим при выводе.

Язык управления представляет собой множество правильно построенных формул {F} над состояниями продукций и бинарными операциями между ними, среди которых выделены следующие проверки условий: последовательная (•), одновременная (, ) и альтернативная (; ). Такие формулы называются управляющими, а множество продукций с заданной на нем управляющей формулой — системой структурированных продукций.

Опишем неформально процесс вывода в Рr с управляющей формулой F на некотором шаге t. Для каждого шага вывода t по F формируется множество А_r, которое состоит из

где

s) — множество продукций, помеченных состоянием +, т.е. продукций, условия которых должны быть истинны на текущем шаге вывода r;

t) — множество продукций, помеченных состоянием -, т.е. продукций, условия которых должны быть ложны на шаге вывода r;

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

После проверки условий A_r распадается на два непересекающихся подмножества:

где и множества всех активированных продукций с истинными и ложными условиями применимости соответственно.

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

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

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

Приведенная контекстно-свободная грамматика порождает язык:

Введем над этой грамматикой управляющую формулу, которая описывается выражением

где ()* задает итеративное применение правил p2, p3 p4.

Данное выражение может быть изображено сетью переходов на рис.1.6

Рис. 1.6. Сеть переходов для языка управления

В результате использования управляющего языка множество слов будет представлять собой язык {aⁿbⁿcⁿ|n³ 1}, который не является контекстно - свободным.

Как видно даже из этого небольшого примера язык управления применением правил позволяет значительно упрощать основные продукции.

⇐ Предыдущая 15 16 17 18 192021 22 23 24 Следующая ⇒