Разработка фреймово-продукционной модели синтеза цифровых автоматов на основе метода спецификации состояний и ее программная реализация средствами реляционной СУБД

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

Актуальность темы

.

Решение практических задач по синтезу автоматов подразумевает использование значительной доли эвристики. Одна из первых серьезных попыток была предпринята С. Колдуэллом [8] в развитие идеи Д. Хаффмэна [42]. Однако этот подход нельзя отнести к числу детерминированных. Обещающий шаг на пути детерминизации процесса синтеза автоматов сделан А. А. Талем [30]. По объективным причинам работа была прервана, и характер ее продолжения не очевиден. Предложенный в [22] подход является эффективным инструментом эвристики [25]. Но с увеличением размерности решаемых задач трудности нарастают.

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

Использование логической [31] модели применительно к синтезу автоматов не очевидно. Возможность развития предикатного метода [7] в плане автоматизации процедуры синтеза требует специальных исследований. Для рассматриваемых объектов наиболее подходят фреймовые структуры данных [21, 11], которые в настоящее время приобрели широкое применение в различных областях.

Цель работы.

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

Достижение поставленной цели требует решения задач:

1. Выбор базового метода синтеза автоматов, хорошо адаптируемого к автоматизации.

2. Разработка фреймово-продукционной модели синтеза автоматов, заданных на неформальном (естественном) языке.

3. Выбор инструментального средства для реализации разработанной модели.

4. Создание интерпретатора экспертной системы синтеза автоматов. Методы исследований.

В работе использованы методы теории автоматов, теории фреймов, компьютерное моделирование с привлечением современных инструментальных средств.

Научная новизна работы:

1. Разработана фреймово-продукционная модель синтеза автоматов.

2. Проведено погружение предложенной модели в среду реляционной СУБД.

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

Проведенные исследования позволяют сделать обобщающий вывод о правомерности разработанных принципов автоматизированной реализации исходной (базовой) модели синтеза автоматов. При этом дело не в названиях выбранных инструментальных средств — Access, SQL, Visual Basic. Вместо Access может быть взята и другая инструментальная СУДЕ, обладающая как минимум указанными свойствами [33]. Тогда объем необходимых программных доработок оказывается приемлемым для создания экспертной системы синтеза автоматов малыми силами и в сжатые сроки.

Практическая значимость работы.

Существующие в настоящее время методы синтеза автоматов, например, метод с использованием' языка регулярных выражений, либо метод с использованием языка логики предикатов, обладают существенным недостатком: задание на синтез автомата должно быть представлено на специализированном языке. Как показывает практика, эта задача довольно проблематична для пользователя. Для рассматриваемого в диссертации метода, синтез проводится по заданию, заданному на неформальном (естественном) языке. Пользователю необходимо определить параметры задания и указать правила смены состояний автомата и получаемой выходной последовательности. Такой подход является для него более привлекательным. Предложенный метод использован для построения прототипа интерпретатора экспертной системы синтеза автоматов по неформальному заданию.

Результаты использованы в учебном процессе кафедры Компьютерных систем и информационной безопасности КГТУ им. А. Н. Туполева (КАИ).

На защиту выносится:

1. Разработка фреймово-продукционной модели синтеза автоматов.

2. Обоснование возможности погружения фреймовой модели в среду реляционной СУБД, на примере Microsoft Access.

3. Разработка языка присоединенных процедур.

4. Разработка прототипа (исследовательской версии) интерпретатора экспертной системы синтеза автоматов.

Апробация результатов работы.

Основные результаты работы докладывались и обсуждались на научно-технической конференции «IX Всероссийские Туполевские чтения студентов» (Казань, 2000 г.), Казанском городском семинаре «Методы моделирования» (Казань, 2001;2005 г.), Республиканской научно-практической конференции.

Интеллектуальные системы и информационные технологии" (Казань, 2001 г.), XIII Международной конференции «Проблемы теоретической кибернетики» (Казань, 2002 г.), V Международной научно-практической конференции «Новые информационные технологии и системы» (Пенза, 2002 г.), Международной научно-практической конференции IEEE AIS'03 (Геленджик, 2003 г.).

Публикации.

Основное содержание диссертации опубликовано в 9 работах, включая 4 статьи [17, 18, 27, 28], 4 тезиса докладов [13, 14, 15, 16] и 1 компьютерный практикум [26].

Структура и объем диссертации

.

Диссертационная работа состоит из введения, четырех глав и заключения. Она изложена на 101 странице, содержит 25 рисунков и 57 таблиц. Библиографический список включает 42 наименования.

Основные результаты диссертационной работы:

1. Проведен анализ существующих методов синтеза автоматов и обоснован выбор базового метода для его реализации в интерактивном режиме.

2. Разработана фреймово-продукционная модель синтеза автоматов по неформальному заданию. Приведена структурная схема модели. Показаны спецификация разработанных фреймов, особенности их заполнения и взаимодействия.

3. Проведено погружение фреймово-продукционной модели в среду реляционной СУБД. Обоснован выбор СУБД Microsoft Access для реализации погружения. Показаны особенности представления таблиц-фреймов в виде таблиц базы данных. Рассмотрена взаимосвязь фреймов с помощью встроенных средств СУБД.

4. Разработан язык присоединенных процедур — язык арифметическо-логических выражений. Описаны основные части языка: переменные, константы, операции, выражения. Выделены два вида выражений: логические и арифметические. Представлены правила записи предложенных выражений, а также алгоритм их обработки.

5. Реализован интерпретатор экспертной системы синтеза автоматов по неформальному заданию. Представлена функциональная схема разработанной программной системы. Приведены результаты тестирования на ряде примеров. Разработано руководство пользователя по работе с системой.

Результаты диссертации использованы в учебном процессе кафедры Компьютерных систем и информационной безопасности КГТУ им. А. Н. Туполева (КАИ).

ЗАКЛЮЧЕНИЕ

.