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

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

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

РАЗРАБОТКА ФРЕЙМОВО-ПРОДУКЦИОННОЙ МОДЕЛИ СИНТЕЗА ЦИФРОВЫХ АВТОМАТОВ НА ОСНОВЕ МЕТОДА СПЕЦИФИКАЦИИ СОСТОЯНИЙ И ЕЕ ПРОГРАММНАЯ РЕАЛИЗАЦИЯ СРЕДСТВАМИ РЕЛЯЦИОННОЙ СУБД

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

численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Казань-2006

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

им. А.Н. Туполева

Научный руководитель:

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

Официальные оппоненты:

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

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

Ведущая организация:

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

Защита состоится 20 октября 2006 г. в 14 часов на заседании диссертационного совета Д 212.079.01 в Казанском государственном техническом университете им. А.Н. Туполева по адресу: 420111, г. Казань, ул. К. Маркса, 10.

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

Автореферат разослан « И »сс*с?Лс>Ъх 2006 г.

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

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

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

. .к

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

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

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

Использование логической модели, предложенной А. Теем, П. Грибомоном и Ж. Луи в работе «Логический подход к искусственному интеллекту» в 1990 году, применительно к синтезу автоматов не очевидно. Возможность развития предикатного метода, описанного Б.А. Трахтенбротом и

H.Е. Кобринскнм в работе «Введение в теорию конечных автоматов» в 1962 году, в плане автоматизации процедуры синтеза требует: специальных исследований. Для рассматриваемых объектов наиболее подходят фреймовые структуры данных, предложенные X. Уэно и М. Исидзука в работе «Представление и использование знаний» в 1989 году, которые в настоящее время приобрели широкое применение в различных областях.

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

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

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

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 году приводится теорема: «Проблема синтеза автомата в общем случае алгоритмически неразрешима». Из приведенной теоремы следует, что если не пытаться сузить каким-либо образом допустимые способы задания на синтезируемый автомат (т.е. язык, на котором описано задание), то лишена смысла всякая попытка найти приемы не только синтеза автомата, реализующего это задание, но даже и ответа на вопрос, существует ли такой автомат. Однако можно столь сильно сузить язык, что любое задание,

выраженное на этом языке, явится заведомо выполнимым автоматом, поэтому останется лишь проблема синтеза.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

л*,5*"' г>(з*. После замены состояний специфицирующими их кортежами

было получено рекурсивное описание структуры знаний:

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

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

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

граф состояний;

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

и каждому допустимому значению входа х* ставится в соответствие

согласно заданию кортеж {...)* —> 5*, Импликация (—*) реализуется

поиском во фрейме спецификаций по ключу

КЕГ = {...)*.

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

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

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

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

ФреймЛ

<* * Li • ■ * NL

1 1 Г | .1 1

Фрейд ТЛЛ

RCLt

TSLi

Е^З CZD Cj=3

AT

Фрейм R.SU J '

ОЬГ

IU . Г 1

Фрейм XI

AT

TSNL

Фрейм

кси

Фрейм Т5И

RSLf

Фрейм RSLI

U path

£

_PU £

Фрейм АТ

RCNL

]L Фрейм TSNL

' PNL RSNL

Фрейм

ксыь

Фрейм

X Q

I □

z □

s □

Фрейм PNL'

X □

I

D

z □

s □

n

Фрейм . RSNL

Фрейм Lfpath

Рис. 1

Таблица 1

Имя фрейма Семантика фрейма

А Концептуальный целевой фрейм автомата :

AT Тип автомата

RSIf Правила сопряжения областей с лабиринтом i

PNL- ■ Параметры вне лабиринтов .; ■

RSNL Правила спецификации вне лабиринтов ,

TSNL Таблица спецификации вне лабиринтов

RCNL Правила слодования вне лабиринтов

TJNL Таблица переходов вне лабиринтов

PLt Параметры в лабиринте I

Li path Пути в лабиринте ( -

RSL( Правила спецификации в лабиринте (

TSLl Таблица спецификации в лабиринте (

RCLt Правила следования в лабиринте 1

TJLl Таблица переходов в лабиринте 4

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

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

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

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

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

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

В общем случае Фрейм:

<слот 1>

<слот 2> * * *

<слот п> Слот:

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

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

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

Таблица 2

Части слота Название атрибута Имя поля записи БД Назначение поля

Имя слота Имя слота NamePNL{PL) Определяет имя слота

Значение слота Тип данных Format_PNL(PL) Определяет тип данных слога. Может принимать значения: - integer - целый • bool - булев - symbol - символьный - count - счетчик - присоединенная процедура (арифметико-логическое выражение) - <...> - ссылка в этом же фрейме на слот, имя которого указано в скобках

Значение Va!ue_PNL(PL) Определяет значение слота. Поле задает; - значение - список значений - выражение

Метка Label_PNL(PL) Определяет наличие (отсутствие) слота в задании. Может принимать одно из двух значений: - present - слот используется в задании • absent - слот не используется в задании

Фрейм (табл. 3) определяет правила спецификации состояний в

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

лабиринта.

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

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

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

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

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

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

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

Таблица 3

Части слота Название атрибута Имя поля записи Назначение поля

Имя слота Имя слота Name_RSNL Определяет имя слота (имя правила)

Значение слота X . Environment_X_RSNL Определяет значение входа в текущем такте

X. En v ironment_X2_RSNL Определяет значение входа в следующем такте

Z. Operation_Z2_RSNL Определяет значение выхода в следующем такте

SPACE Operations PAC E_RS N L Определяет область, в которую переходит автомат

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

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

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

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

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

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

Дополненная структурная схема фреймово-продукционной модели представлена на рис. 2.

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

Рис. 2

Системная процедура генерации фрейма ЕЛЗЫЬ

Для реализации фрейма ЕИЗЫЬ используются фреймы РЫЬ и КЭЫЬ, которые обрабатываются следующим образом:

1) для всех слотов фрейма ИЯМЬ добавить записи в ЕК5МЬ по правилам табл.4;

2) ЕСЛИ значение параметра рассматриваемого слота является выражением, ТО запускается процедура определения значений этого выражения с использованием фрейма РЫЬ.

____ Таблица 4

ERSNL RSNL

Xм = x"

X* xk

„ ZL1

SB 1ы

Space*"1 = Space1"1

Zk в Zk

1" - Ik

Space1 - Spacek

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

РЬИ.

Рис. 2

Системная процедура генерации фрейма Т8№£,

При генерации фрейма ТБЫЬ используются данные фрейма ЕКЗИЬ по правилам табл.5.

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

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

ТО 8к := "-".

- ЕСЛИ автомат остается в прежней области вне лабиринта,

ТО := "значение следующего по счетчику номера состояния для данной области".

__ Таблица 5

темь ЕК5М>

Хк-' — Хк^

хк К X1-'

гы = Zk'i

1ы = 1ы

г;к = 2к

1к = 1к

Брасс1 = Брасск

5к — еслиЗрасе* = Пили ¿2

[ счетчик

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

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

S"*1, ХкЛ Х1"2, Zk*\ Ik*\ Space1*1, Хк; Х\ Хы.

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

Spacek = "NL";

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

Таблица 6

TJNL TSNL PNL

s1-1 = sk

хы хк

хы

Z*'1 =

Г1

Space"-' Space1

Хк Хк

ХК Хк

хы = X"

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

Z\ Ik, Spacek.

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

XWersnl - Xkhtjnl, i е {О, 1, 2};

^ ERSNL — TJNL, гк-1 _ ГЫ

1 ERSNL ~ 1 TJNLJ

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

Таблица 7

TJNL ERSNL

Z* s= ZL

1к з? lk

Space" = Space"

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

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

Xt TSNL ~ X TJNL» • 6 {О» О;

Z TSNL ~ TJNL»

i tsnl = i tjnlj

It к

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

Таблица 8

TJNL 1 TSNL

S* Sk

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

ТБЫЬ

ч „ у" Z4" ™Л.1 J —Spacei.— Имя „слшз.„ Формат Значение

1 01 00 попе none NL

Xlk BOOL 00

- | 00 1 1] 1 none ! попе f IL Xlk BOOL 01

xik BOOL 11

Xlk BOOL 10

О

TJNL

НИ

00

| попе"

NL

)

т

Процедура

выбора значений Xt

00

О!

s X X*'1 z1' r"' Space1'' x" X ■' X1 z T- Space" Sl

1 1 01 00 none none L-NL-i" 01 ! 00 01 01 none LI

J L L i k

.....H 01 [ 00 | none none | 01 1 1 01 | none 1 LI 1

ERSNL i SQL-запрос поиска записи Ж к J ! 1 I I L

X1'1 z"" X Space""1 . 2LL. lk 1 .-Spaced

none 00 none none 01 none 01 none LI

Рис.3

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

/ этап. Обработка области вне лабиринта. Для всех слотов фрейма ТЛч1Ь ■добавить в TJNL_T.iL слот по правилам табл.9.

Таблица 9

TJNL TJL TJNL

s*71 =s sn

xk = X* '

z" = Zk

sk as sk

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

Таблица 10

TJN TJL TJL PL

sri = Sk-i

хк = xk

zk = выделение выхода из lk, если Space1 <> «LI» Zk, если Space* *» «LI»

s" = SK

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подписано в печать 4.09.06 г. Печать ризографическая. Гарнитура Times. Формат бумаги 60x90/16. Объем 1 п.л. Тираж 100 экз. Заказ № 121

Информационно-технологический центр ACO (КСЮИ) 420039, г. Казань, ул. Исаева, 12 тел. 542-45-84

ВВЕДЕНИЕ.

Глава 1. НОВЫЕ ТЕНДЕНЦИИ В ОБЛАСТИ АБСТРАКТНОГО

СНТЕЗА АВТОМАТОВ.

§1.1. Классификация основных методов.

§1.2. Формальные методы.

§1.3. Неформальные методы.

§ 1.4. Метод синтеза, основанный на спецификации состояний.

§1.5. Выводы по первой главе.

Глава 2. ФРЕЙМОВО-ПРОДУКЦИОННАЯ МОДЕЛЬ СИНТЕЗА

АВТОМАТОВ.

§2.1. Синтез автомата как задача искусственного интеллекта.

§2.2. Предлагаемая модель. Область вне лабиринтов.

§2.3. Предлагаемая модель. Области лабиринтов. Заключительный этап.

§2.4. Выводы по второй главе.

Глава 3. ВОПРОСЫ ПРОГРАММНОЙ РЕАЛИЗАЦИИ

ПРЕДЛАГАЕМОЙ МОДЕЛИ.

§3.1. Задачи исследования.

§3.2. Пример погружения модели в среду Microsoft Access.

§3.3. Язык присоединенных процедур и его реализация.

§3.4. Реализация системных процедур модели синтеза автоматов.

§3.5. Расширение функциональных возможностей системы.

§3.6. Выводы по третьей главе.

Глава 4. ИССЛЕДОВАТЕЛЬСКАЯ ВЕРСИЯ РАЗРАБОТАННОЙ

ИНТЕРАКТИВНОЙ СИСТЕМЫ СИНТЕЗА АВТОМАТОВ

§4.1. Программная система.

§4.2. Результаты тестирования.

§4.3. Руководство пользователя.

§4.4. Пример задания на синтез автомата.

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

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

Решение практических задач по синтезу автоматов подразумевает использование значительной доли эвристики. Одна из первых серьезных попыток была предпринята С. Колдуэллом [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. Реализован интерпретатор экспертной системы синтеза автоматов по неформальному заданию. Представлена функциональная схема разработанной программной системы. Приведены результаты тестирования на ряде примеров. Разработано руководство пользователя по работе с системой.

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

98

ЗАКЛЮЧЕНИЕ

1. Агибалов Г.П. Синтез автоматов по конечно-определенным словарным функциям // Алгоритмы решения задач дискретной математики. -Томск: Изд-во Том. ун-та, 1979. - С. 160-164.

2. Айзерман М.А., Гусев Л.А., Розоноэр Л.И. и др. Логика. Автоматы. Алгоритмы. -М.: Физматгиз, 1963.

3. Ангер С. Асинхронные последовательностные схемы. М.: Наука, 1977.

4. Базилевский Ю.Я. Вопросы теории временных логических функций // Вопросы теории математических машин. М.: Физматгиз, 1958.

5. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962.

6. Клини С. Представление событий в нервных сетях и конечных автоматах // Автоматы. М.: Иностр. лит., 1956.

7. Кобринский Н.Е., Трахтенброт Б.А. Введение в теорию конечных автоматов. -М.: Физматгиз, 1962.

8. Колдуэлл С. Логический синтез релейных устройств. М.: Иностр. лит., 1962.

9. Кузнецов О.П. Релейные устройства и конечные автоматы // Структурная теория релейных устройств. М.: Изд-во АН СССР, 1963.

10. Мелихов А.Н. Ориентированные графы и конечные автоматы. М.: Наука, 1971.

11. Минский М. Фреймы для представления знаний. М.: Энергия, 1979.

12. Моисил Гр.К. Алгебраическая теория дискретных автоматических устройств. М.: Иностр. лит., 1963.

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

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

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

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

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

18. Нейман Дж фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971.

19. Попов Э.В. Экспертные системы. М.: Наука, 1987.

20. Представление и использование знаний / Под ред. X. Уэно., М. Исидзука. М.: Мир, 1989.

21. Райхлин В.А. К синтезу автомата по неформальному заданию // Кибернетика и системный анализ, 1994. № 4. - С. 29-41.

22. Райхлин В.А. Конструктивное моделирование систем. Казань: Изд-во ФЭН (Наука), 2005. - 304 с.

23. Райхлин В.А. Неформальные модели синтеза. Базовые понятия и принципы // Вестник КГТУ им. А.Н. Туполева. Казань: Изд-во Казан, гос. техн. ун-та, 2000. - № 3. - С. 53-58.

24. Райхлин В.А. Синтез цифровых автоматов в переходном режиме. -Казань: Изд-во Изд-во Казан, гос. техн. ун-та, 1998.

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

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

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

28. Спивак М.А. Алгоритмы абстрактного синтеза автоматов для расширенного языка регулярных выражений // Известия АН СССР. Техническая кибернетика, 1965. -№1.

29. Таль А.А. Анкетный язык и абстрактный синтез минимальных последовательных машин // Автоматика и телемеханика, 1964. № 6. -1965. -№3-4.

30. Тей А., Грибомон П., Луи Ж. и др. Логический подход к искусственному интеллекту. М.: Мир, 1990.

31. Тоффоли Т., Марголус Н. Машина клеточных автоматов. М.: Мир, 1991.-280 с.

32. Ульман Дж. Основы систем баз данных. М.: Финансы и статистика, 1983.-336 с.

33. Шалыто А.А. Автоматное проектирование программ. Алгоритмизация и программирование задач логического управления // Теория и системы управления, 2000. № 6. - С. 63-81.

34. Burks A.W., Copy J.M. The logical design of an idealized general-purpose computer. // J. Franclin Inst, 1956. V.261. - №3-4

35. Burks A.W., Wang H. The logic of automata. Univ. Michigan, Ann. Arbor, Mich. Eng. Res. Inst, 1956.

36. Burks A.W., Wright G.B. Theory of logical nets. // Proc. IRE. V.41. -1953.-№4.

37. Chebotarev A.N. Construction of an automaton from a formula of the monadic first-order theory of the natural numbers. // Kibernetika sistemny analiz, 2001. -№ 4. P. 91-106.

38. Chebotarev A.N. Synthesizing of the procedural representation of the automaton specified in the logical language L*.II // Kibernetika sistemny analiz, 1997.-№6.-P. 115-126.

39. Chebotarev A.N. Syntnesis of the procedural representation of an automaton specified in the logical language L*.I // Kibernetika sistemny analiz, 1997. -№4.-P. 60-74.

40. Church A. Application of recursive arithmetic in the theory of computers and automata. Univ. Michigan, 1958.

41. Huffman D.A. The synthesis of sequential switching circuits // J. Franklin Inst, 1954.-V. 257.-№3-4.