Размещено на http://www.allbest.ru/

На правах рукописи

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

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

Специальность: 05.13.18 - Математическое моделирование, численные методы и комплексы программ

МОРОЗОВ Андрей Владимирович

Казань - 2006

Работа выполнена в Казанском государственном техническом университете им. А.Н. Туполева

Научный руководитель: Доктор физико-математических наук, профессор Райхлин Вадим Абрамович

Официальные оппоненты: Доктор физико-математических наук, профессор Соловьев Валерий Дмитриевич

Доктор технических наук, профессор Галиев Шамиль Ибрагимович

Ведущая организация: Научно исследовательский институт математики и механики им. Н.Г Чеботарева (г. Казань)

Защита состоится « 20 » октября 2006 г. в 14 часов

на заседании диссертационного совета Д 212.079.01

в Казанском государственном техническом университете им. А.Н. Туполева по адресу: 420111, г.Казань, ул. К. Маркса, 10

С диссертацией можно ознакомиться в библиотеке Казанского государственного технического университета им. А.Н. Туполева

Автореферат разослан «____»__________2006 г.

Ученый секретарь диссертационного совета

доктор физико-математических наук, профессор П.Г. Данилаев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Тематика диссертации. В диссертации исследуется вопрос автоматизации процесса синтеза детерминированных автоматов. Рассматриваются вопросы применения современных инструментальных средств для этих целей.

Актуальность темы. Решение практических задач по синтезу автоматов подразумевает использование значительной доли эвристики. Одна из первых серьезных попыток была предпринята С. Колдуэлом в работе «Логический синтез релейных устройств» в 1962 году как развитие идеи Д. Хафмэна. Однако этот подход нельзя отнести к числу детерминированных. Обобщающий шаг на пути детерминизации процесса синтеза автоматов сделан А.А. Талем в работе «Анкетный язык и абстрактный синтез минимальных последовательностных машин» в 1965 году. По объективным причинам работа была прервана, и характер ее продолжения не очевиден. Предложенный В.А. Райхлиным в работе «К синтезу автомата по неформальному заданию» в 1994 году подход является эффективным инструментом эвристики. Но с увеличением размерности решаемых задач трудности нарастают.

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

Использование логической модели, предложенной А. Теем, П. Грибомоном и Ж. Луи в работе «Логический подход к искусственному интеллекту» в 1990 году, применительно к синтезу автоматов не очевидно. Возможность развития предикатного метода, описанного Б.А. Трахтенбротом и Н.Е. Кобринским в работе «Введение в теорию конечных автоматов» в 1962 году, в плане автоматизации процедуры синтеза требует специальных исследований. Для рассматриваемых объектов наиболее подходят фреймовые структуры данных, предложенные Х. Уэно и М. Исидзука в работе «Представление и использование знаний» в 1989 году, которые в настоящее время приобрели широкое применение в различных областях.

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

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

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

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

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

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

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

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

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

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

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

Проведенные исследования позволяют сделать обобщающий вывод о правомерности разработанных принципов для реализации автоматизированной системы исходной базовой модели синтеза автоматов. При этом дело не в названиях выбранных инструментальных средств - 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 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

автомат база данные фреймовый

Во введении обосновывается актуальность темы диссертации, дается определение цели и задач исследования, приводится перечень основных результатов, выносимых на защиту. Дана структура диссертации.

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

Абстрактная теория автоматов в ее современном виде в основном сформировалась в 50-60-е годы. Среди этих методов по-прежнему теоретически значим метод регулярных выражений, развитый В.М. Глушковым. Его практическое использование затруднено применением правила подчинения мест. Некоторое облегчение вносит графическая интерпретация метода, показанная О.П. Кузнецовым и позднее усовершенствованная А.Н. Мелиховым, и ее алгебраическое развитие (М.А. Спивак). Менее известны другие методы: исчисления предикатов (Б.А. Трахтенброт), временных логических функций (Ю.Я. Базилевский), примитивно-рекурсивных функции (А. Черч), полей Галуа (Гр. Моисил).

Автомат - объект, имеющий множество внутренних состояний и множество изменений входов, работа которого носит детерминированный характер. В случае «широкого языка заданий» существует проблема алгоритмической неразрешимости синтеза автоматов. В книге «Логика. Автоматы. Алгоритмы» Айзермана М.А., Гусева Л.А., Розоноэра Л.И. и др. в 1963 году приводится теорема: «Проблема синтеза автомата в общем случае алгоритмически неразрешима». Из приведенной теоремы следует, что если не пытаться сузить каким-либо образом допустимые способы задания на синтезируемый автомат (т.е. язык, на котором описано задание), то лишена смысла всякая попытка найти приемы не только синтеза автомата, реализующего это задание, но даже и ответа на вопрос, существует ли такой автомат. Однако можно столь сильно сузить язык, что любое задание, выраженное на этом языке, явится заведомо выполнимым автоматом, поэтому останется лишь проблема синтеза.

В качестве такого языка можно принять, например, язык регулярных формул, т.е. считать, что задания всегда выражаются в терминах представления событий, заданных регулярными выражениями. Алгоритм синтеза автомата, заданного таким способом, заведомо существует. Это показано в книге Айзермана М.А., Гусева Л.А., Розоноэра Л.И. «Логика. Автоматы. Алгоритмы». Другим примером языка, относительно которого установлено, что все выраженные на нем задания заведомо реализуемы автоматом, и для которого существует алгоритм синтеза, является предикатный язык описанный Кобринским Н.Е. и Трахтенбротом Б.А. в книге «Введение в теорию конечных автоматов» в 1962 году.

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

Поэтому оправданы попытки разработок неформальных подходов к синтезу автоматов при широком языке задания. Известны две такие попытки: анкетный подход, предложенный Талем А.А. в статье «Анкетный язык и абстрактный синтез минимальных последовательных машин» в 1964-1965 годах и табличный метод с применением языка спецификации состояний описанный в статье Райхлина В.А. «Синтез цифровых автоматов в переходном режиме» в 1988 году.

Также в первой главе на примерах рассмотрены описанные выше методы. Делаются выводы о достоинствах и недостатках этих методов.

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

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

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

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

Все вышеизложенное можно позволяет сделать следующие выводы:

· формальные языки практически пригодны для ограниченного круга заданий;

· возникают трудности представления задания на синтез «заказчиком»;

· при большой глубине и количестве регулярный выражений синтез автомата становится трудоемким;

· для реальных задач сложно учесть все параметры.

Принципиальное отличие рассмотренных неформальных моделей в том, что задание на синтез автомата может быть описано на языке, близком естественному. Это ведет к тому, что «заказчик» не должен владеть каким-то специализированным языком, что является для него наиболее привлекательным. Задача синтеза целиком перекладывается на "исполнителя". На передний план выдвигается разработка подходящего инструментального средства.

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

В этих методах присутствует эвристичность. Так в методе Таля А.А. у «исполнителя» нет точной последовательности задания вопросов «заказчику». Тот или иной вопрос задается в соответствии с ранее полученными ответами. В методе Райхлина В.А. эвристика явно присутствует в одном из параметров кортежа, специфицирующего состояния, - ИНДЕКСе. Однако, если задание на синтез автомата содержит большое число параметров, возникает проблема «человеческого фактора». Человек просто не в состоянии охватить, просмотреть и обработать весь объем получаемой информации. Поэтому для применения данного метода необходимо привлекать программные средства, используя методы искусственного интеллекта.

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

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

Разработка формата таблицы спецификации состояний синтезируемого автомата. Интерпретация атрибутов (семантика полей записей) таблицы уникальна для каждого задания на синтез. В процессе интерпретации возможно появление дополнительных атрибутов, определение которых необходимо для реализации этапа 3.

Детализация условий задания на синтез в виде совокупности правил.

Определение формата ключа поиска переходов из каждого специфицированного состояния и правил формирования этого ключа.

Генерация системы по результатам п. 1 - 3.

Заполнение таблицы спецификации состояний. Выполняется сгенерированной системой автоматически в соответствии с п. 1, 2.

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

Пока не будет выполнено условие замкнутости, необходимо корректировать п. 1 - 3 с последующим повторением п. 4 - 6.

Однако реализация этого подхода довольно затруднительна, поскольку каждое задание на синтез требует разработки своей таблицы спецификации состояний. Поэтому неформальная модель синтеза автомата требует адекватной структуризации знаний для ее восприятия искусственным интеллектом. Для этого необходимо формализовать правила перехода между состояниями на множестве допустимых изменений входа. Такая формализация была представлена Райхлиным В.А. в книге «Конструктивное моделирование систем». Канонические рекурсии для автомата Мили были представлены в виде продукции . После замены состояний специфицирующими их кортежами было получено рекурсивное описание структуры знаний:

.

Соответственно ядро фреймово-продукционной модели синтеза автоматов составляют:

1) фрейм спецификации состояний записями вида

,

где - специфицирующий кортеж для . Этот фрейм представляет граф состояний;

2) фрейм переходов, в котором каждой записи

,

и каждому допустимому значению входа ставится в соответствие согласно заданию кортеж . Импликация (>) реализуется поиском во фрейме спецификаций по ключу

.

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

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

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

Фрейм А

- - -

L?

SIL?

- - -

NL

Фрейм TJL?

Фрейм RSI?

Фрейм TJNL

RCL?

TSL?

AT

OL?

IL?

AT

TSNL

RCNL

Фрейм RCL?

Фрейм TSL?

Фрейм AT

Фрейм TSNL

Фрейм RCNL

RSL?

PL?

PNL

RSNL

Фрейм RSL?

Фрейм PL?

Фрейм PNL

Фрейм RSNL

L? path

X

I

Z

S

X

I

Z

S

Фрейм L?path

Рис. 1

Таблица 1

Имя фрейма	Семантика фрейма
A	Концептуальный целевой фрейм автомата
AT	Тип автомата
RSI?	Правила сопряжения областей с лабиринтом ?
PNL	Параметры вне лабиринтов
RSNL	Правила спецификации вне лабиринтов
TSNL	Таблица спецификации вне лабиринтов
RCNL	Правила слодования вне лабиринтов
TJNL	Таблица переходов вне лабиринтов
PL?	Параметры в лабиринте ?
L? path	Пути в лабиринте ?
RSL?	Правила спецификации в лабиринте ?
TSL?	Таблица спецификации в лабиринте ?
RCL?	Правила следования в лабиринте ?
TJL?	Таблица переходов в лабиринте ?

На основе построенной модели было проведено моделирование «вручную» процесса синтеза автомата для ряда заданий. Для всех них зафиксировано полное отсутствие коллизий при детерминированности процесса и правильности получаемого решения.

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

Предлагаемая фреймово-продукционная модель принимается за основу разработки интерпретатора экспертной системы синтеза автоматов. Часть фреймов модели заимствует эвристику пользователя, вполне доступную «широкому кругу». В остальном процесс реализуется автоматически. Система в целом допускает погружение в среду реляционной СУБД.

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

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

При погружении фреймово-продукционной модели в среду СУБД Access, каждый фрейм представляется отношением базы данных табличного вида. Каждая запись такой таблицы - слот фрейма, поля записи - атрибуты слота. Характерная особенность таблиц-фреймов в сравнении с обычными таблицами-отношениями БД состоит в том, что значения одного и того же атрибута (тип данных и др.) могут принадлежать разным доменам. Значения атрибутов могут интерпретироваться и как ссылки на значения других слотов. Это обуславливает необходимость внесения определенных корректив в принятый механизм реляционных СУБД. В частности, каждый слот фреймов PNL и PL?, должен интерпретироваться в соответствии с доменами своего типа данных, а значения некоторых атрибутов фрейма RSNL берутся из одноименных слотов PNL.

В общем случае

Фрейм:

<слот 1>

<слот 2>

…

<слот n>

Слот:

<имя слота> <значение слота>

Значение слота для разных фреймов за редким исключением имеет неодинаковые атрибуты.

Проиллюстрируем указанные положения на двух примерах. Формат слота фрейма PNL отвечает табл. 2.

Таблица 2

Части слота	Название атрибута	Имя поля записи БД	Назначение поля
Имя слота	Имя слота	Name_PNL(PL)	Определяет имя слота
Значение слота	Тип данных	Format_PNL(PL)	Определяет тип данных слота. Может принимать значения: - integer - целый - bool - булев - symbol - символьный - count - счетчик - присоединенная процедура (арифметико-логическое выражение) - <…> - ссылка в этом же фрейме на слот, имя которого указано в скобках
	Значение	Value_PNL(PL)	Определяет значение слота. Поле задает: - значение - список значений - выражение
	Метка	Label_PNL(PL)	Определяет наличие (отсутствие) слота в задании. Может принимать одно из двух значений: - present - слот используется в задании - absent - слот не используется в задании

Фрейм RSNL (табл. 3) определяет правила спецификации состояний в области вне лабиринта. При его разборе происходит автоматически генерация фрейма TSNL - таблица спецификации состояний автомата в области вне лабиринта.

Значения полей X и X. могут задаваться:

- значением соответствующего слота фрейма параметров задания PNL;

- безразличным значением «-»;

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

Задание значений поля Z. также носит нетривиальный характер. Это поле может быть задано:

- значением соответствующего слота фрейма параметров задания PNL;

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

Таблица 3

Части слота	Название атрибута	Имя поля записи	Назначение поля
Имя слота	Имя слота	Name_RSNL	Определяет имя слота (имя правила)
Значение слота	X	Environment_X_RSNL	Определяет значение входа в текущем такте
	X.	Environment_X2_RSNL	Определяет значение входа в следующем такте
	Z.	Operation_Z2_RSNL	Определяет значение выхода в следующем такте
	SPACE	Operation_SPACE_RSNL	Определяет область, в которую переходит автомат

Взаимосвязь фреймов осуществляется с помощью стандартных средств Access. В качестве этих средств выступают язык запросов SQL и встроенный в Access язык программирования Visual Basic. Связь фреймов осуществляется:

- прямым обращением из одного фрейма к другому с использованием функций Visual Basic;

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

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

Также в третьей главе предлагается возможная реализация языка присоединенных процедур. Слоты присоединенных процедур во фреймах PNL, PL? и RSNL представлены в виде арифметико-логических выражений. Организацию таких процедур целесообразно возлагать на пользователя через посредство «дружественного» интерфейса. При этом действия пользователя сводятся к удобной для него записи логических и арифметических выражений. Пользователь указывает правила либо процедуры, с помощью которых система может самостоятельно определить неизвестные параметры. Для реализации такого подхода предложен ограниченный пользовательский язык - язык арифметическо-логических выражений.

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

Приводятся алгоритмы и схемы работы разработанных системных процедур.



Рис. 2

Системная процедура генерации фрейма ERSNL

Для реализации фрейма ERSNL используются фреймы PNL и RSNL, которые обрабатываются следующим образом:

1) для всех слотов фрейма RSNL добавить записи в ERSNL по правилам табл.4;

2) если значение параметра рассматриваемого слота является выражением,

ТО запускается процедура определения значений этого выражения с использованием фрейма PNL.

Таблица 4

ERSNL			RSNL
Xk-2	=	Xk-2
Xk-1	=	Xk-1
Xk	=	Xk
Zk-1	=	Zk-1
Ik-1	=	Ik-1
Spacek-1	=	Spacek-1
Zk	=	Zk
Ik	=	Ik
Spacek	=	Spacek

Работу алгоритма поясняет рис.2.

Рис. 2

Системная процедура генерации фрейма TSNL

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

Значения параметра Sk определяются по следующим правилам:

- ЕСЛИ происходит смена области функционирования автомата, т.е. автомат переходит из области вне лабиринта в область лабиринта,

ТО Sk := “-“ .

ЕСЛИ автомат остается в прежней области вне лабиринта, ТО Sk := “значение следующего по счетчику номера состояния для данной области“.

Таблица 5

TSNL			ERSNL
Xk-1	=	Xk-2
Xk	=	Xk-1
Zk-1	=	Zk-1
Ik-1	=	Ik-1
Zk	=	Zk
Ik	=	Ik
Spacek	=	Spacek
Sk	=

Системная процедура генерации фрейма TSNL

В этой процедуре исходными данными являются фреймы PNL, TSNL, ERSNL. Процесс генерации TJNL разбивается на три этапа.

I этап. Определение параметров

Sk-1, Xk-1, Xk-2, Zk-1, Ik-1, Spacek-1, Xk; Xk, Xk-1.

1) выбрать все записи фрейма TSNL, где

Spacek = ”NL”;

2) для всех значений Xk фрейма PNL добавить записи в TJNL по правилам табл.6.

Таблица 6

TJNL			TSNL			PNL
Sk-1	=	Sk
Xk-1	=	Xk
Xk-2	=	Xk-1
Zk-1	=	Zk
Ik-1	=	Ik
Spacek-1	=	Spacek
Xk			=	Xk
Xk			=	Xk
Xk-1	=	Xk

II этап. Определение значений параметров

Zk, Ik, Spacek.

1) для всех записей TJNL выбирать из ERSNL запись, где

Xk-iERSNL = Xk-iTJNL, i {0, 1, 2};

Zk-1ERSNL = Zk-1TJNL;

Ik-1ERSNL = Ik-1TJNL;

2) используя найденную запись, выполнить действия для TJNL табл.7.

Таблица 7

TJNL			ERSNL
Zk	=	Zk
Ik	=	Ik
Spacek	=	Spacek

III этап. Определение значений параметра Sk.

1) для всех записей TJNL выбирать из TSNL запись, где

Xk-iTSNL = Xk-iTJNL, i {0, 1};

ZkTSNL = ZkTJNL;

IkTSNL = IkTJNL;

SpacekTSNL=SpacekTJNL

2) используя найденную запись выполнить действия для TJNL табл.8:

Таблица 8

TJNL			TSNL
Sk	=	Sk

Работу алгоритма поясняет рис.3. Здесь не отображен третий этап алгоритма. Он реализуется по той же схеме, что и второй этап.

Рис.3

Системная процедура получения общей таблицы переходов

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

I этап. Обработка области вне лабиринта. Для всех слотов фрейма TJNL добавить в TJNL_TJL слот по правилам табл.9.

Таблица 9

TJNL_TJL			TJNL
Sk-1	=	Sk-1
Xk	=	Xk
Zk	=	Zk
Sk	=	Sk

II этап. Обработка области лабиринта. Для всех слотов фрейма TJL добавить в TJNL_TJL слот по правилам табл.10.

Таблица 10

TJN_TJL			TJL	PL
Sk-1	=	Sk-1
Xk	=	Xk
Zk	=	выделение выхода из Ik, если Spacek < > «L1»	Zk, если Spacek = «L1»
Sk	=	Sk

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

Проведенные исследования позволяют сделать обобщающий вывод не только о правомерности использованных принципов реализации исходной модели, но и о целесообразности такого использования в общем случае автоматов с лабиринтами. При этом дело не в названиях - Access, SQL, Visual Basic. Вместо Access может быть взята и другая инструментальная СУДБ. При этом объем необходимых программных доработок оказывается приемлемым для создания экспертной системы синтеза автоматов с лабиринтами малыми силами и в сжатые сроки.

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

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

В заключении сформулированы основные результаты диссертации.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

Основное содержание диссертации опубликовано в работах

1. Морозов А.В. Интерпретация языка спецификаций состояний при синтезе цифровых автоматов // IX Всероссийские Туполевские чтения студентов: Научно-техническая конференция, Казань, 25-26 октября 2000 года: Тезисы докладов. Том II. Казань: Изд-во Казан. Гос. Техн. Ун-та, 2000. С. 32.

2. Райхлин В.А., Морозов А.В. Фреймово продукционная модель синтеза автоматов // Вестник КГТУ им.А.Н.Туполева. - 2001. - №3.

3. Морозов А.В. Моделирование процесса синтеза автоматов как задача искусственного интеллекта // Интеллектуальные системы и информационные технологии: Труды республиканской научно-практической конференции, Казань, 30 октября-1 ноября 2001 года. Казань: Отечество, 2001. С. 77-78.

4. Морозов А.В. О возможности погружения фреймовой структуры модели синтеза автоматов в среду реляционной СУБД // Тезисы докладов XIII Международной конференции «Проблемы теоретической кибернетики». 2002. Том II. С. 127.

5. Морозов А.В. К реализации фреймовой модели синтеза автоматов // Труды V Международной научно-практической конференции «Новые информационные технологии и системы». 2002. С. 162-164.

6. Морозов А.В. О реализуемости фреймовой модели синтеза автоматов в инструментальной среде СУБД // Вестник КГТУ им.А.Н.Туполева. - 2003. - №2. С. 63-68.

7. Райхлин В.А., Морозов А.В., Вершинин И.С, Абрамов Е.В. Интеллектуальные модели синтеза // Труды конференции IEEE AIS'03, CAD-2003. - М.: Физматлит, 2003. Т.2. С. 158-171.

8. Морозов А.В. Реализация системных процедур модели синтеза автоматов // Эволюционное моделирование / Под ред. В.А. Райхлина. Труды Казанского городского семинара «Методы моделирования». Вып. 2 - Казань: Из-во «ФЭН» («Наука»), 2004. С. 288-296.

9. Райхлин В.А., Морозов А.В. Интерактивная система синтеза автоматов. Компьютерный практикум. - Казань: АСО (КСЮИ), 2006. 32 С.

Размещено на Allbest.ru

...