Содержание к диссертации
Введение
Глава 1. НОВЫЕ ТЕНДЕНЦИИ В ОБЛАСТИ АБСТРАКТНОГО СИНТЕЗА АВТОМАТОВ 7
1.1. Классификация основных методов 7
1.2, Формальные методы 8
1.3. Неформальные методы 9
1.4. Метод синтеза, основанный на спецификации состояний 11
1.5. Выводы по первой главе 26
Глава 2. ФРЕИМОВО-ПРОДУКЦИОННАЯ МОДЕЛЬ СИНТЕЗА АВТОМАТОВ 28
2.1. Синтез автомата как задача искусственного интеллекта 28
2.2. Предлагаемая модель. Область вне лабиринтов 30
2.3. Предлагаемая модель. Области лабиринтов. Заключительный этап 35
2.4. Выводы по второй главе 40
Глава 3. ВОПРОСЫ ПРОГРАММНОЙ РЕАЛИЗАЦИИ ПРЕДЛАГАЕМОЙ МОДЕЛИ 42
3.1. Задачи исследования 42
3.2, Пример погружения модели в среду Microsoft Access 45
3.3. Язык присоединенных процедур и его реализация 49
3.4. Реализация системных процедур модели синтеза автоматов 55
3.5. Расширение функциональных возможностей системы 64
3.6. Выводы по третьей главе 66
Глава 4. ИССЛЕДОВАТЕЛЬСКАЯ ВЕРСИЯ РАЗРАБОТАННОЙ ИНТЕРАКТИВНОЙ СИСТЕМЫ СИНТЕЗА АВТОМАТОВ 68
4.1. Программная система 68
4.2. Результаты тестирования 71
4.3. Руководство пользователя 79
4.4. Пример задания на синтез автомата 93
ЗАКЛЮЧЕНИЕ 97
БИБЛИОГРАФИЯ 98
- Классификация основных методов
- Синтез автомата как задача искусственного интеллекта
- Пример погружения модели в среду Microsoft Access
- Программная система
Введение к работе
Тематика диссертации. В диссертации исследуется вопрос автоматизации процесса синтеза детерминированных автоматов. Рассматриваются вопросы применения современных инструментальных средств для этих целей.
Актуальность темы. Решение практических задач по синтезу автоматов подразумевает использование значительной доли эвристики. Одна из первых серьезных попыток была предпринята С. Колдуэлом в работе «Логический синтез релейных устройств» в 1962 году как развитие идеи Д. Хафмэна. Однако этот подход нельзя отнести к числу детерминированных. Обобщающий шаг на пути детерминизации процесса синтеза автоматов сделан А.А. Талем в работе «Анкетный язык и абстрактный синтез минимальных последовательностных машин» в 1965 году. По объективным причинам работа была прервана, и характер ее продолжения не очевиден. Предложенный В.А. Райхлиным в работе «К синтезу автомата по неформальному заданию» в 1994 году подход является эффективным инструментом эвристики. Но с увеличением размерности решаемых задач трудности нарастают.
Рост сложности практических задач делает актуальной автоматизацию процедуры синтеза автоматов по неформальному заданию, что связано с поиском адекватного представления знаний в системе искусственного интеллекта.
Использование логической модели, предложенной А. Теем, П. Грибомоном и Ж. Луи в работе «Логический подход к искусственному интеллекту» в 1990 году, применительно к синтезу автоматов не очевидно. Возможность развития предикатного метода, описанного Б.А. Трахтенбротом и Н.Е. Кобринским в работе «Введение в теорию конечных автоматов» в 1962 году, в плане автоматизации процедуры синтеза требует специальных исследований. Для рассматриваемых объектов наиболее подходят фреймовые структуры данных, предложенные Х. Уэно и М. Исидзука в работе «Представление и использование знаний» в 1989 году, которые в настоящее время приобрели широкое применение в различных областях.
Цель работы. Разработка конструктивного подхода к построению интерактивной системы синтеза цифровых автоматов, функционирование которых задано на языке близком естественному.
Достижение поставленной цели требует решения следующих задач:
1. Выбор базового метода синтеза автоматов, хорошо адаптируемого к автоматизации.
2. Разработка фреймово-продукционной модели синтеза автоматов, заданных на неформальном (естественном) языке.
3. Выбор инструментального средства для реализации разработанной модели.
4. Создание интерпретатора экспертной системы синтеза автоматов.
Методы исследований. В работе использованы методы теории автоматов, теории фреймов, компьютерное моделирование с привлечением современных инструментальных средств.
Научная новизна работы:
-
Разработана фреймово-продукционная модель синтеза автоматов.
-
Проведено погружение предложенной модели в среду реляционной СУБД.
-
Разработан язык присоединенных процедур фреймово-продукционной модели, предлагающий пользователю удобный инструмент для описания исходного задания, заданного на языке близком естественному.
Проведенные исследования позволяют сделать обобщающий вывод о правомерности разработанных принципов для реализации автоматизированной системы исходной базовой модели синтеза автоматов. При этом дело не в названиях выбранных инструментальных средств – Access, SQL, Visual Basic. Вместо Access может быть взята и другая инструментальная СУДБ, обладающая как минимум указанными свойствами. Тогда объем необходимых программных доработок оказывается приемлемым для создания экспертной системы синтеза автоматов малыми силами и в сжатые сроки.
Практическая значимость работы. Существующие в настоящее время методы синтеза автоматов, например, метод с использованием языка регулярных выражений, либо метод с использованием языка логики предикатов, обладают существенным недостатком: задание на синтез автомата должно быть представлено на специализированном языке. Как показывает практика, эта задача довольно проблематична для пользователя. Для рассматриваемого в диссертации метода, синтез проводится по заданию, заданному на неформальном (естественном) языке. Пользователю необходимо определить параметры задания и указать правила смены состояний автомата и получаемой выходной последовательности. Такой подход является для него более привлекательным. Предложенный метод использован для построения прототипа интерпретатора экспертной системы синтеза автоматов по неформальному заданию.
Результаты использованы в учебном процессе кафедры Компьютерных систем и информационной безопасности КГТУ им. А.Н. Туполева (КАИ).
На защиту выносится:
1. Разработка фреймово-продукционной модели синтеза автоматов.
2. Обоснование возможности погружения фреймовой модели в среду реляционной СУБД.
4. Разработка языка присоединенных процедур.
5. Разработка прототипа (исследовательской версии) интерпретатора экспертной системы синтеза автоматов.
Апробация результатов работы. Основные результаты работы докладывались и обсуждались на научно-технической конференции «IX Всероссийские Туполевские чтения студентов» (Казань, 2000г.), Казанском городском семинаре «Методы моделирования» (Казань, 2001-2005гг.), Республиканской научно-практической конференции «Интеллектуальные системы и информационные технологии» (Казань, 2001г.), XIII Международной конференции «Проблемы теоретической кибернетики» (Казань, 2002г.), Международной научно практической конференции «Новые информационные технологии и системы» (Пенза, 2002г.), Международной научно-технической конференции IEEE AIS’03 (Геленджик, 2003г.).
Публикации. Основное содержание диссертации опубликовано в 9 работах, включая 4 статьи и 4 тезиса докладов и 1 компьютерный практикум.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав и заключения. Она изложена на 98 страницах, содержит 34 рисунка и 50 таблиц. Библиографический список включает 37 наименований.
Классификация основных методов
В данной главе приводится обзор известных методов абстрактного синтеза цифровых автоматов и дается их классификация. Показываются достоинства и недостатка этих методов. Обосновывается выбор базового метода синтеза автомата для его реализации в интерактивном режиме. Выбранный метод иллюстрируется на множестве представительных заданий.
1.1. Классификация основных методов
Абстрактная теория автоматов в ее современном виде в основном сформировалась в 50-60-е годы. Достаточное представление о развитых методах синтеза конечных автоматов дает уже обзор [9]. Среди этих методов по-прежнему теоретически значим метод регулярных выражений, развитый В.М. Глушковым [2]. Его практическое использование затруднено применением правила подчинения мест. Некоторое облегчение вносит графическая интерпретация метода, показанная О.П. Кузнецовым в [2] и позднее усовершенствованная А.Н. Мелиховым [10], и ее алгебраическое развитие (М.А. Спивак [29]). Менее известны другие методы: исчисления предикатов (Б.А. Трахтенброт [7]), временных логических функций (ЮЛ. Базилевский [4]), примитивно-рекурсивных функции (А. Черч [41]), полей Галуа (Гр. Моисил [12]).
Из современных работ можно выделить:
метод синтеза автоматов по конечно определенным словарным функциям [1],
метод построения автомата, представленного в терминах состояний и функции перехода, заданной на логическом языке [38, 39,40],
метод синтеза автомата по неформальному заданию с применением языка спецификации состояний [22,25]. Серьезное внимание последнее время уделяется вопросам автоматного
проектирования программ [34] и применения клеточных автоматов [19] для целей моделирования [32].
Следствием известных теорем С. Клини [6] является утверждение о том, что необходимое и достаточное условие существования конечного автомата -представимость его описания в виде регулярного выражения. Это определило основное направление исследований по абстрактному синтезу автоматов, которое фактически себя исчерпало уже к началу 70-х годов прошлого века.
Новый импульс к возрождению исследований по абстрактному синтезу дали успехи последних лет в области искусственного интеллекта. Это заставило вновь обратить внимание на давние работы Д. Хафмена [42] и С. Колдуэлла [6, 8] и положило начало нашим исследованиям, основанным на методе спецификации состояний автомата.
Основные методы синтеза автоматов можно разделить на два класса:
1) формальные:
метод регулярных выражений разработанный Глушковым В.М.
графический метод Кузнецова О.П.
метод синтеза автоматов с использованием языка логики предикатов Трахтенброта Б.А.
2) неформальные:
анкетный подход, предложенный Талем А.Н.
метод синтеза автоматов по неформальному заданию предложенный Райхлиным В.А.
Далее приводится сравнительный анализ обоих классов.
Синтез автомата как задача искусственного интеллекта
В данной главе рассматривается возможный подход к построению диалоговой системы синтеза автомата по неформальному заданию. Предлагается фреймово-продукционная модель для автоматизации процесса синтеза автоматов. Делается вывод о возможности применения ее для разработки экспертной системы синтеза автоматов.
2.1. Синтез автомата как задача искусственного интеллекта
Неизбежность эвристики при синтезе автомата связана с тем, что при достаточной широте языка задания и бесконечной области определения задача синтеза в общем случае алгоритмически неразрешима [2, 30]. Усложнение заданий делает актуальной проблему автоматизации процесса синтеза. Ее решение связано с адекватным представлением знаний в системе искусственного интеллекта (ИИ). База знаний системы содержит факты и эвристические правила. Обычно правила имеют вид продукций «условие -действие» [20]. Вопрос в том, как структурировать эти знания.
Определенный в [24] язык спецификации состояний автомата является формально-подобной системой. Однако он может стать рабочим инструментом логического вывода [31] только после уникальной для каждого задания интерпретации. Поэтому логическая модель как таковая в данном случае непригодна. Предпочтителен выбор объектно-ориентированной, или фреймовой модели. Это вытекает из объектной трактовки конечного автомата и его состояний [22, 25]:
1) автомат - объект, определенный перечнем внутренних состояний и указанием порядка следования между ними на множестве изменений входа.
Каждому полному состоянию s, х (s - номер внутреннего СОСТОЯНИЯ, X значение входа) отвечает свое значение выхода z;
2) внутреннее состояние автомата - объект, специфицированный кортежем хы - xk, I, zk (к - номер такта, I - индекс). Вектор v = хы - хк, 1 определяет условия перехода в состояние sk со значением выхода zk = f (v). Компоненты индекса - значения параметров задания. Их определение -предмет эвристики.
Фреймы - структуры данных для представления подобных концептуальных объектов [11,21].
К тому же реализация подхода синтеза автомата с использованием языка спецификации состояний автомата довольно затруднительна, поскольку каждое задание на синтез требует разработки своей таблицы спецификации состояний. Поэтому неформальная модель синтеза автомата, рассмотренная в первой главе, требует адекватной структуризации знаний для ее восприятия искусственным интеллектом. Для этого необходимо формализовать правила перехода между состояниями на множестве допустимых изменений входа. Такая формализация была представлена в [23].
Пример погружения модели в среду Microsoft Access
В данной главе рассматриваются вопросы реализации фреймовой модели синтеза автоматов с лабиринтами в адекватной среде на примере СУБД Microsoft Access. Показывается представление некоторых таблиц-фреймов в виде модифицированных таблиц БД и их взаимосвязь. Предлагается язык присоединенных процедур и его возможная реализация с помощью языка программирования Visual Basic. Рассматриваются вопросы реализации системных процедур фреймово-продукционной модели синтеза автоматов. Приводятся алгоритмы работы этих процедур. Даются необходимые пояснения. Делается вывод возможности реализации рассматриваемой модели в среде инструментальной СУБД.
3.1. Задачи исследования
Несмотря на классичность тематики цифровых автоматов, автоматизация процесса их абстрактного синтеза в условиях неформальности задания до сих пор проблематична. Рассмотренный во второй главе подход с позиции искусственного интеллекта создает необходимые теоретические предпосылки к построению экспертных систем синтеза достаточно широкого класса автоматов. При этом возникает актуальный вопрос о принципиальной разрешимости задачи реализации разработанной фреймово-продукционной модели на базе имеющихся инструментальных средств.
Предпринятая попытка реализации модели средствами языка Microsoft Visual C++ с включением в него языка запросов SQL показала принципиальные трудности построения автоматизированной системы синтеза автоматов на подобной основе. Сложность реализации структуры таблиц-фреймов только средствами объектно-ориентированного языка затрудняет организацию поиска в этих таблицах. Приемлемым путем преодоления этих трудностей является погружение модели в инструментальную среду реляционной СУБД [33]. Для фреймовых структур данных такое решение органично. Оно привлекательно не только в
плане синтеза автоматов, но и в смысле возможной экстраполяции. Его развернутое обсуждение применительно к автоматам с акцентированием особенностей трактовки фреймов как отношений интеллектуальной базы данных с элементами знаний в виде продукционных правил является предметом настоящей главы. Рассмотрение проводится на примере погружения модели в среду Microsoft Access для класса автоматов с лабиринтами [22], когда область вне лабиринтов и сам лабиринт единственны.
Программная система
Данная глава посвящена описанию пользовательских аспектов исследовательской версии разработанной интерактивной системы синтеза автоматов. Представлены разработанные формы фреймов. Приведено руководство по работе с системой.
4.1. Программная система
Система синтеза (Sinthesis) реализована в инструментальной СУБД Microsoft Access с использованием языка программирования Microsoft Visual Basic.
Sinthesis - предназначена для синтеза таблицы перехода автомата заданного на неформальном языке. Система реализует фреймово-продукционную модель, представленную и описанную во второй и третьей главах настоящей работы.
Функциональная схема реализованной системы иллюстрируется нарис. 4.1.
1. В первом блоке реализуется процедура ввода и обработка задания для
области вне лабиринта.
2. Во втором и третьем блоках реализованы процедуры ввода и обработки задания для первой и второй лабиринтных областей,
3. В четвертом блоке реализованы процедуры совмещения областей вне лабиринта и лабиринтов, а также получение канонической таблицы переходов автомата.
1. На основе фреймов, заполненных пользователем (PNL, RSNL) генерируется расширенный фрейм правил спецификации состояний области вне лабиринта ERSNL.
2. На основе заполненного пользователем фрейма PNL и полученного фрейма ERSNL генерируется фрейм спецификации состояний области вне лабиринта TSNL.
3. Используя фрейм правила слодования вне лабиринтов RCNL, который в данной системе реализован программно, заполненного пользователем фрейма PNL и полученного фрейма TSNL генерируется фрейм таблица переходов области вне лабиринта TJNL
Область вне лабиринта рис. 4.26.
1. На основе фреймов, заполненных пользователем (PL, Lpath) генерируется фрейм правила спецификаций области в лабиринте RSL
2. На основе заполненного пользователем фрейма PL и полученного фрейма RSL генерируется фрейм таблица спецификации состояний лабиринтной области TSL.
3. Используя фрейм правила слодования вне лабиринтов RCL, который в данной системе реализован программно, заполненного пользователем фрейма PL и полученного фрейма TSL генерируется фрейм таблица переходов области вне лабиринта TJL.
Получение совмещенной таблицы переходов автомата состоит из следующих этапов:
1. На основе фрейма правил сопряжения областей RSI, который в данной системе реализован программно, полученные фреймы TJNL и TJL совмещаются.
2. Далее на основе совмещенных таблиц TJNL и TJL генерируется общая таблица переходов автомата - концептуальный целевой фрейм автомата А. 3. На последнем этапе фрейм А преобразуется в каноническую таблицу переходов автомата.
Алгоритмы генерации фреймов ERSNL, TSNL, TJNL, совмещения областей и получения общей таблицы переходов были рассмотрены в третьей главе настоящей работы были описаны.
