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

• Автор: Келемен, Йозеф
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 73 c. : ил

ГЛАВА I. ФОРМАЛЬНЫЕ ГРАММАТИКИ И ПРОДУКЦИОННЫЕ

СИСТЕМЫ

1.1. Некоторые задачи искусственного интеллекта

и их связь с продукционными системами

1.2. Обзор существующего положения

1.3. Некоторые нерешенные проблемы

1.4. Постановка задачи

Глава II. КОНВЕНЦИОНАЛЬНЫЕ ГРАММАТИКИ

2.1. Целенаправленность и управление выводом

в грамматиках

2.2. Основные оцределения

2.3. Иерархические свойства языков, порожденных к-грамматиками
2.4. Грамматическая сложность к-грамматик и
языков
2.4.1. Оцределения
2.4.2. Независимость
2.4.3. Теоремы
2.5. Выводы
Глава III. ОБОБЩЕННЫЕ КОНВЕНЦИОНАЛЬНЫЕ ГРАММАТИКИ
3.1. Обучение и индуктивный вывод
3.2. Основные определения
3.3. Исследование грамматической сложности ок-грамматик и языков

3.4« Выводы
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА

В последние годы цроявляется тенденция к использованию вычислительных машин в областях, связанных не с классическими вычислениями, а с обработкой разного рода символьной информации. В частности, подобные задачи возникают в тех системах, работа которых основывается на знаниях, хранимых в памяти вычислительных систем. Это требует создания специальных средств для представления знаний и манипулирования ими. В настоящее время в качестве языков для представления знаний, как правило, используются либо логические исчисления, либо сетевые представления различного типа (семантические сети [13] , фреймы СЗ] , сценарии [34] ). В качестве языков манипулирования данными в подавляющем большинстве случаев используются различного рода продукционные системы [II] , [373
Продукционные системы являются естественным развитием модели формальных грамматик, созданных еще во второй половине 50-х годов
Н.Хомским [9] . Другим источником возникновения современных продукционных систем является теория секвенциальных систем, которая развивалась еще в работах Э.Поста, а затем была использована в ставших классическими исследованиях Э.Ньюэлла и Г.Саймона [33]
Однако, имевшиеся до настоящего'времени исследования в области классификации типов формальных грамматик и секвенциальных систем, а также в области анализа и синтеза этих средств не могут быть прямо использованы для формализации существующих сейчас языков манипулирования знаниями. Это связано с тем, что продукционные системы, использованные для этих целей, имеют ряд отличительных особенностей (например, наличие управления при выборе продукций) , которые не позволяют использовать для них ранее построенные модели.

и, следовательно:
Неравенство *3) очевидно для всех
обыкновенных контекстно-свободных языков.
Теорема 2,4
Существует последовательность языков И-п}п~ , для
которых:

Доказательство :
Пусть , Язык контекстно-свободный
6*“ с
( / ). Следовательно, существует такой вывод^=/4 =>о1А(2>
для которого это означает, что
Равенство ^ вытекает из анализа к-грамматики с множеством продукций
лг А
<3.^ - /4
: А Ь
Очевидно, ЧТО 4 У - /. и то, что .Из неравенства 4^7 получим