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

В последние годы проявляется тенденция к использованию вычислительных машин в областях, связанных не с классическими вычислениями, а с обработкой разного рода символьной информации. В частности, подобные задачи возникают в тех системах, работа которых основывается на знаниях, хранимых в памяти вычислительных систем. Это требует создания специальных средств для представления знаний и манипулирования ими. В настоящее время в качестве языков для представления знаний, как правило, используются либо логические исчисления, либо сетевые представления различного типа (семантические сети [13J, фреймы ЕЗ], сценарии С34J). В качестве языков манипулирования данными в подавляющем большинстве случаев используются различного рода цродукционные системы СИ], Г 37J .

Продукционные системы являются естественным развитием модели формальных грамматик, созданных еще во второй половине 50-х годов Н. Хомским [9]. Другим источником возникновения современных продукционных систем является теория секвенциальных систем, которая развивалась еще в работах Э. Поста, а затем была использована в ставших классическими исследованиях Э. Ньюэлла и ГЧСаймона С33] .

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

Это определяет актуальность данного исследования, в результате которого предлагается новая формальная модель продукционных систем, более адекватная реально существующим системам.

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

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

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

Научная новизна работы заключается в следующем:

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

2) Для к-грамматик исследована проблема выводимости, дван анализ порождаемых ими языков и построена классификация этих грамматик, аналогичная известной ранее классификации грамматик Хомского.

— 6.

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

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

5) Даны некоторые оценки сложности, связанные с необходимым числом продукционных правил, объемом памяти для хранения промежуточных результатов вывода и с необходимым для определения данной к-грамматики числом символов.

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

Результаты работы докладывалист на:

1) международной конференции" Искусственный интеллект и информационно-управляющие системы роботов" в Смоленицах (ЧССР) в июле 1980 г.;

2) семинаре по теории автоматов на. кафедре, вычислительной математики и вычислительной техники Естествознательного факультета Университета им. Л. Этвеша в Будапеште (ВНР) в апреле 1981 г.;

3) международной конференции по теории автоматов, — языков и математических систем в Шалготаряне (ВНР) в мае 1984 г.;

4) конференции молодых математиков и программистов Унив. им. Л. Этвеша в Будапеште. (ВНР) в мае 1984 г.;

5) кафедре теоретической кибернетики Математико-физического факультета Унив. им. Коменского в Братиславе (ЧССР) в 1983 и 1984 годах;

6) семинаре лаборатории теории и проектирования больших систем ВЦ Ш СССР в 1981, 1983 и 1984 годах.

По теме диссертации автором опубликовано II работ: С203 — [29] и работа [321 .

Диссертация состоит из введения, трех глав, заключения и списка литературы.

Основные выводы настоящей работы можно сформулировать следующим образом:

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

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

3) Введен набор грамматических мер сложности для к-грамматик и ок-грамматик и доказана их взаимная независимость.

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

.