Распознавание конечных детерминированных автоматов методом зацикливания

Кунявская, Анна Наумовна

Распознавание конечных детерминированных автоматов методом зацикливания тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Кунявская, Анна Наумовна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Саратов МЕСТО ЗАЩИТЫ

2004 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Распознавание конечных детерминированных автоматов методом зацикливания»

Автореферат диссертации на тему "Распознавание конечных детерминированных автоматов методом зацикливания"

На правах рукописи //»"---

Кунявская Анна Наумовна

Распознавание конечных детерминированных автоматов методом зацикливания

01.01.09 - дискретная математика и математическая кибернетика

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

Саратов - 2004

Работа выполнена на кафедре теоретических основ информатики и информационных технологий Саратовского государственного университета им. Н.Г. Чернышевского

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

доктор технических наук,

профессор

Сытник Александр Александрович

профессор

Твердохлебов Владимир Александрович

кандидат физико-математических наук доцент

Башмаков Василий Аркадьевич

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

доктор технических наук,

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

Институт проблем управления РАН (Москва)

Защита диссертации состоится 2004 г. в

/е- на заседании диссертационного совета К 212.243.02 в Саратовском государственном университете (410012, г. Саратов, ул.Астраханская 83).

на засе-

С диссертацией можно ознакомиться в Научной библиотеке СГУ.

Автореферат разослан

Г.

Ученый секретарь диссертационного совета к.ф.-м.н., доцент

Корнев В.В.

ВВЕДЕНИЕ

Конечные детерминированные автоматы составляют один из важнейших классов математических моделей для динамических систем с конечным множеством состояний. Конечные автоматы не только используются для представления функционирования реальных систем (технических, биологических, экономических, организационных и т.п.), но и включается как важнейшая компонента в более сложные дискретные детерминированные математические модели, например, машины Тьюринга и автоматы с магазинной памятью. Практическое и теоретическое значение автоматных моделей в решении задач проектирования и технического диагностирования, познания процессов формирования и передачи сигналов в биологических системах, систематизации и оптимизации управляющих воздействий в экономике и т.д. стало причиной интенсивных исследований по теории автоматов. Исследованию теории автоматов, а также вопросам их возможного применения в различных отраслях науки и техники посвящено большое количество работ отечественных и зарубежных авторов. Следует отметить исследования Дж, фон Неймана, АГилла, В.М.Глушкова, С.В.Яблонского, П.П.Пархоменко, В.Б.Кудрявцева, БАТрахгенброта, АМ.Богомолова, М.Ф.Каравая, Д.В Сперанского, ВАТвердохлебова, ААСытника.

Разнообразие возникших задач, подходов к их решению, научных позиций исследователей привело к выделению классов автоматов (автоматы типов Мили и Мура, автоматы Медведева, автономные автоматы, автоматы с конечной глубиной памяти, (п, П1, 1) -автоматы и т.д.), а также к разработке различных математических способов их задания (табличное задание, графы автоматов, автоматные матрицы, логические уравнения, формулы языка регулярных выражений, задание автомата композицией автоматов).

Потребность в использовании моделей в виде конечных детерминированных автоматов для реальных объектов с большим числом состояний привела к развитию теории структурных автоматов, в которой абстрактная форма автомата А = (Б, X, У, 8, X), где S, X и У - соответственно множества состояний, входных и выходных сигналов, а 8 и функции переходов и выходов , заменялась струк-

турной формой, то есть, композицией преобразователей сигналов и элементов памяти.

Первое, принципиально важное, представление абстрактного автомата на пути к его структурному заданию, определяется следующей схемой:

х е X

5 е в

Комбинац. уеУ.

часть

в'

ПАМЯТЬ

у = X X) б' = 5 (Б, Х)

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

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

показано A.M. Богомоловым и В.А. Твердохлебовым, в этом

с да® ЯАЦШЙЪДЧЛШЧ БИБЛИОТЕКА ! (¡.Петербург I ОЭ 1007» (

ское изменение состояний. Состояния, не вошедшие в циклы, можно исключить из анализа и оставить для анализа только состояния, не вошедшие в циклы.

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

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

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

1. Описание и обоснование классификации конечных детерминированных автоматов на основании учета специфических свойств комбинационных частей автоматов.

2. Построение и обоснование математической модели процесса зацикливания автомата. Изучение функционирование автомата с изменениями состояний в циклах. Решение установочной задачи для автоматов с зацикливанием.

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

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

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

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

Апробация работы и публикации. Основные результаты диссертации докладывались на Международной конференции «Компьютерные науки и информационные технологии» (Саратов. 2002 г.), на Всероссийской конференции "Телематика - 2001 (Санкт-Петербург, 2001), на Всероссийской конференции "Телематика - 2003 (Санкт-Петербург, 2003), на семинарах в Саратовском государственном университете, в Саратовском государственном социально-экономическом университете, в Институте проблем точной механики и управления РАН, в Центральном научно-исследовательском институте измерительной аппаратуры. По теме диссертации опубликовано 5 статей.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы (68 наименований) и двух приложений. Объем работы 143 страницы машинописного текста.

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

Кодирование элементов множества состояний в двоичными векторами размерности И;, множества входных сигналов X двоичными векторами размерности и множества выходных сигналов У двоичными векторами размерности п3 позволяет представить комбинационную часть набором функции алгебры логики вида :

Принимаемая классификация построена на классификации функций 1 <

I ^ И/, Лу , 1 £ Щ , по их принадлежности классам Поста: К0 (функции сохраняющие 0), К1 (функции сохраняющие 1), Кь (линейные функции), Кт (монотонные функции), К (самодвойственные функции). В качестве памяти автомата рассматривается набор из п1 элементов задержки сигнала на один такт. Здесь же рассматривается наличие сочетаний свойств, то есть принадлежность функций алгебры логики классам вида

у ¡- - где а имеет значение а, если класс определяется наличием у функции

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

Задание конечного детерминированного автомата в виде трех множеств в, X, У и двух функций удобно для теоретического рассмотрения зако-

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

В качестве основных свойств положения отдельного элемента в структуре выбраны: управляемость входом элемента (вход элемента является внешним входным узлом автомата); наблюдаемость выхода элемента. В основу построения эксперимента по распознаванию автомата в заданном семействе структурных конечных детерминированных автоматов (например, при интерпретации семейства автоматов как математического описания класса рассматриваемых дефектов) положена декомпозиция задачи распознавания на три задачи: задачу локального проявления дефекта > на элементе, предполагаемым неисправным; задачу управления локальным проявлением дефекта (управления внешними входными сигналами); задачу наблюдения проявлением дефекта на внешних выходах автомата.

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

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

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

Наблюдаемость выхода задержки означает, что ее выходной узел является внешним выходным узлом автомата. Если входной узел задержки оказывается внешним входным узлом автомата, то задержка полагается управляемой. Управляемость элементом задержки сигнала на такт понимается как отождествление её выходного узла с внешним входным узлом автомата. Следовательно, из управляемости получаем наблюдаемость задержки по входу.

В соответствии с этим разработана алгебра композиции автоматов и построена классификация типов размещения элементов в структуре автомата. Предлагаются следующие операции: операция изолированного раздвоения узла, операция связного узла раздвоения узла, систематизированные в форме восьми операций с узлами структурного автомата. Операция изолированного раздвоения узла. Узел V представляется двумя изолированными друг от друга узлами V, и ^ с указанием ориентации от узла V1 к узлу V. Операция связного раздвоения узла. Узел V представляется двумя связными узлами V, и У2 с указанием ориентации от узла V, к узлу V

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

Операция 1 включает задержки изолированным раздвоением внутреннего узла: внутренний узел V изолированно раздваивается на узлы V, и Vкоторые отождествляются соответственно с входным и выходным узлами задержки.

Операция 2 включает задержки изолированным раздвоением внешнего выходного узла: внешний выходной узел V изолированно раздваивается на узлы V, и V, которые отождествляются соответственно с входным и выходным узлами задержки (узел У2 оказывается внешним выходным узлом).

Операция 3 включения задержки изолированным раздвоением внутреннего узла и связного раздвоения входного узла задержки: внутренний узел V изолированного раздваивается на узлы V\ и V, которые отождествляются соответственно с входным и выходным узлами задержки, а узел V1 связно раздваивается на узлы V, и У12. Узел У22 оказывается внешним выходным узлом структуры автомата.

Операция 4 включения задержки изолированным раздвоением внешнего входного узла: внешний входной узел V изолированного раздваивается на узлы V, и V, которые отождествляются соответственно с входным и выходным узлами задержки (узел V, оказывается внешним выходным узлом).

Операция 5 включения задержки изолированным раздвоением внутреннего узла и связным раздвоением полученных узлов: внутренний узел V изолированного раздваивается на узлы V\ И У,2, узлы V, и V связно раздваиваются на узлы Уп, УГ2 и V,, У,2,2, а узлы Уп и У22 отождествляются соответственно с входным и выходным узлами задержки (узлы У12 и У22 оказывается внешними выходными узлами).

Операция 6 включения задержки изолированным раздвоением внешнего входного узла и связным раздвоением второго полученного узла: внешний входной узел V изолированного раздваивается на узлы У1 и V, узел У2 связно раздваиваются на узлы ¥м, У22 , узлы У1 и У21 отождествляются соответственно с входным и выходным узлами задержки (узел У22 оказывается внешним выходным узлом).

Применением операций 1-6 могут быть построены структуры из достаточно большого класса структур конечных детерминированных автоматов. Следующая операция соединения внешнего выходного узла структуры с её внешним входным узлом с помощью задержки сигнала на такт существенно расширяет синтезируемый класс структур конечных автоматов. Операция 7 соединения внешнего выходного узла с внешним входным узлом через задержку сигнала на такт: внешний выходной узел V и внешний входной узел V отождествляются соответственно с входным и выходным узлами задержки.

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

Операция 8. неориентированного внешнего выходного узла: узел V связно раздваивается на узлы V1 и V2 с сохранением узла V и выполнением условия, что в каждый момент времени в узлах V, V1 и V2 сигналы совпадают.

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

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

Теорема 10. В классе (2, 2, 2) - автоматов существует точно один автомат типа Мура: сохраняющий 0; самодвойственный; сильносвязный. Таким автоматом является двоичная задержка сигнала на такт.

Теорема 11. Пусть автомат сохраняет 0, самодвойственный и связный. Тогда

для него минимальными синхронизирующими входными последовательностями являются 01 и 10.

Теорема 12. В классе (2, 2, 2) - автоматов для самодвойственных автоматов свойство сохранять 0 и сохранять 1 эквивалентны.

Эти теоремы иллюстрируют существование связей свойств комбинационных частей автоматов со свойствами процессов функционирования автоматов.

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

Теорема 13. Необходимым и достаточным условием существования решения установочной задачи для конечного детерминировано автомата является условие:

(Уьа'еБ) (Эр еХ ){8(з, р) = д(з\р) V Х(а,р) *Х(*\р)}

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

Основное содержание второй главы диссертации составляет изложение основных положений метода распознавания автомата (в заданном семействе автоматов), базирующихся на приложении периодической последовательности выходных сигналов. А.М. Богомоловым и ВА Твердохлебовым показано, что функционирование конечного детерминированного автомата под воздействием периодической входной последовательности с любым периодом р е X* и рассмотрением связей состояний в и 5(э,р), ее 5,определяется конечным графом с циклами и деревьями, корни которых являются вершинами циклов. В этой работе не исследуются вопросы выбора периодов для периодических последовательностей входных сигналов и определения основных параметров, характеризующих эффективное зацикливание изменений состояний. В связи с этим во второй главе диссертации рассматривается процесс зацикливания на языке графов, поясняются исключения состояний до достижения циклов и исключения состояний после достижения «фактическим» состоянием автомата соответствующего цикла.

Основную идею разработанного метода составляет построение по заданному конечному детерминированному автомату Л = ( в, X, У, 8, X ) такого автомата П , у которого: входными сигналами являются слова р, е X используемые как периоды периодических входных последовательностей; выходными сигналами являются слова , построен-

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

П = Г/57, {р, .*«?/;. &П. 8Л)

где [8] -множество состояний, входящих в циклы, а 5 и Я - новые функции переходов и выходов.

Для автомата А = (Б, X, У, 8, Л) используются два способа расширения функции выходов Л. В первом случае функция . Я расширяется до функции вида но правилу: ( Ух еЯ) ( Ух еХ) ( Ур еХ') Я д:р) = Л (я, х) Я (3 х),р). с

целью уменьшения объема наблюдаемых выходных сигналов автомата, используется также расширение функции до функции вида при котором наблю-

дается только последний выходной сигнал:

( Уз еБ) ( Ух еХ) ( Ур еХ') Я" (э.хр) = Л(3(в,р),х) где функция 8 расширена до функции вида по правилу:

( Уз е8)( Ух еХу Уп #гГ*) хр) = 5(8(з,х),р) к

Предположим, что Х—{Х!,Х2, ... , Хт}. Входная последовательность х / при достаточно большом к ( к> п) для любого начального состояния сформирует последовательность состояний

5(з,х,),8(з,х\).....8(з, х\), (♦)

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

подграфов: (хд,» Он > •••> Сгщ соответственно с циклами С*.....СГ • В пред-

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

С1 /-»"1

и»,' ■•■' С-д,

' ' 'и исключением из анализа вершин, не входящих в циклы.

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

первого или последнего выходного сигнала для каждого периода р и состояния 5, принадлежащего циклу; выходного слова Л (¡5, р) для каждого состояния в цикла и отдельного периода р, некоторых выходных сигналов слова Л & р).

Определение 5. Пусть А = (Б, X, У, 8, Я) - конечный детерминированный автомат и р е X. .. Граф = (з, р р) будем называть графом зацикливания (автомата по периодической входной последовательности с периодом ), если

Правило построения математической модели функционирования автомата в режиме зацикливания. Пусть заданы конечный - детерминированный автомат А = (Б, X, У, <? Л.) и набор слов в алфавите X {р/, Р2, ..., рг}-

1. Для автомата А ~ (5, X, У, 5, А) строятся графы Ср1, Ср2, ... , С?рг •

2. Для каждого графа С7р, I < I ¿Г, определяются числа

3. В графах. выделяются циклы й)[ ( ¿У, - число циклов в графе ).

4. Множество £ состояний автомата А полагаем множеством состояний определяемого автомата (Вариант определения автомата, моделирующего процесс зацикливания).

т, тг «г-

5. Множество входных слов {р >Рг *'">РГ ' ,> где ' = " т 21 автомата А полагается множеством входных сигналов автомата .

6. Пусть ХЦ/^1 ( 1 < I £ г функции, соответствующие множеству периодических входных последовательностей {р^ , р^ , г Рг } . Функцию = О полагаем функцией переходов определяемого автомата.

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

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

мого автомата.

Определение 6. Конечный детерминированный автомат, определяемый пунктами 1-8 для автомата А = (Б, X, У, Л)г будем называть моделью зацикливания автомата А по

Р^ , р ' .....р с параметром V и обозначай^,

входным последовательностям

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

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

В параграфе 3.1 проводится анализ свойств автоматных матриц и степеней таких матриц. Получены условия, определяющие: принадлежность всех состояний автомата циклам при зацикливании одной и той же компоненте связности, принадлежность всех состояний автомата циклам при приложении к автомату периодической последовательности входных сигналов, число состояний автомата, не принадлежащих циклам (число состояний в циклах), при зацикливании изменений состояний автомата для заданной периодической последовательности входных сигналов, наличие циклов в виде петель (циклов длины 1) и циклов длины К.

Систематизация действий по построению графов вида Ор , определяющих процесс зацикливания конечного детерминированного автомата А по периодической входной последовательности р", может быть осуществлена на основе вычисления реакций автомата Q (А, р, V). Такая систематизация ориентированна на автономную интерпретацию выполняемых действий. С точки зрения организации удобной технологии вычислений можно автомат А задавать автоматной матрицей и действия по построению графа Gr представлять действиями со словарными матрицами.

Определение 7. Пусть X— конечный непустой алфавит, X - множество всех слов в алфавите X, M tl M' - матрицы размерности П X П„ где П £ N* , с элементами соответственно niij, tn у сХ , l i,j п: Матрицу U размерности Л X П , у которой каждый элемент 03 ¡j, где 1 < i,j П, определяется равенством

® ij ~ mil > m!j ^ mi2, fn'îjU V Мц t t^lj , где знак умножения обозначает конкатенацию множеств слов, будем называть результатом умножения конкатенацией матрицы M на матрицу и обозначать

Определение 8. Пусть А — (S, X, Y, S, Л) - конечный детерминированный автомат и £ - порядок на множестве его состояний: 5/ Ч S2 -< ... •< Sn при | S | = И . Матрицу МА размерности п X П, в которой каждый эле 1Я fyHД® J S ftjЬ^Пе, л я е т с я равенством будем называть матрицей переходов автомата А.

Для конечных автоматов с большим числом входных сигналов построение процедур зацикливания автоматов практически неэффективно. В связи с этим поиск требующихся процедур зацикливания можно осуществлять при ограничении множества анализируемых последовательностей вхоттных сигналов Полную информацию о процессах зацикливания дают степени матрицы MA: M'a , Л/,.....АГЛ.

Поиск процедур зацикливания на основе анализа входных последовательностей, построенных не из всех возможных входных сигналов, осуществляемых на основе построения и анализа степеней матрицы М(а, wj : M! (a, W) < ^"(а. W) > •••> A/*Yа Ю • При анализе степеней матрицы используются следующие свойства.

Свойство 1. Состояния Si И Sj являются вершинами одного и того же связанного подграфа графа зацикливания Gp, где р , тогда и только тогда, когда р £ nj^ ^

где и m ¡j - элемент матрицы. Л/А.

Свойство 2. Для того, чтобы граф зацикливания G, где р (В X , состоял только из циклов, необходимо и достаточно, чтобы входное слово р в каждом столбце матрицы где К = | р\ содержалось точно один раз.

Свойство 3. Пусть в конечном детерминированном автомате А — (S, X, Y, Ô, Л), где | S | — П ,В (О, 0<О)<П, столбцах матрицы М^а входное слово р , ) р\ = К , не содержится. Тогда не менее чем СО состояний автомата не являются вершинами циклов графа Gp.

Свойство 4. В графе G зацикливания автомата А имеется: подграф с петлей, если р G m* „■ ([ р\ = К, 1 < i ) для элемента матрицы Л/^, подграф с циклом, содержащим точно две вершины, если р £ ТПу С\ rtlji для некоторых элементов ГПу И Шц матрицы Определение. Пусть

А = (S, X, Y, S, X)

- конечный детерминированный автомат и U - { m'a . m'a. ...} - множество степеней матрицы Мл . Для любого W CZX определим оператор Hw, преобразующий матрицу вида В матрицу Hw где элемент h*у матрицы определяется равенством: h^ij — mKij о IV.

Введенный оператор Нш,

исключает из элементов матрицы, к которой он применяется, все слова множестваX*, не принадлежащие множеству слов W.

Свойство 5. Для того, чтобы состояние St автомата А являлось вершиной цикла графа GB, р S )С И | р\ — К, необходимо, чтобы в матрице М^а для любого _/, 1 <j

<п, р g mKv.

На основании свойства 5 преобразованиями матриц можно выделить циклы графа Gp. Для этого к матрице М^а применяется оператор Н/р / . В полученной матрице Hf р ) (М^а) исключаются все пустые столбцы и соответствующие им по состояниям строки до получения матрицы без столбцов, состоящих только из пустых элементов. В полученной матрице имеются строки и столбцы только для такихр- приемниками представленных в матрице состояний.

Построенная матрица циклов определяет как сами циклы, так и , после вычислений с использованием функции выходов автомата, выходные реакции. На этой основе может реа-лизовываться поиск решения установочной задачи.

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

Теорема 14. Пусть А = (S, X, Y, S , Я) - конечный детерминированный автомат и Q ( А, р" , 1 < i £ Г, V ) -модель зацикливания автомата А. Тогда любое решение

р в {р ¿г} установочной задачи для автомата (А, р ' <" Г , V)

является решением установочной задачи для автомата А.

В параграфе 3.3 систематизируется анализ законов функционирования автоматов с целью поиска периодических последовательностей входных сигналов. В основе лежит построение автоматных матриц и возведение матриц в степени. Теоремы обосновывают следующий факт: возведение матрицы в степени на основе конкатенации слов (замена умножения чисел) и теоретико-множественного объединения (замена сложения чисел), позволяет получать связи состояний и их р-преемников (теорема 15), а также наблюдаемые выходные слова (теорема 16).

Теорема 15. Пусть А = (Б, X, У, 5, Л) , где о — ($1, , ... , - конечный детерминированный автомат." »Д/^ - матрицы размерности П X П , где IV/ , И^2 е" Х>, соответственно элементы которых удовлетворяют условиям

Тогда для матрицы выполняется условие

е 1У2 & 5 ($1,р1р2)= где (1 < ц < п).

Теорема 16. Пусть А — (Б, X, У, 8, Л) - конечный детерминированный автомат и 5 = {з/, . Предположим, что для подмножеств определены матри-

цы размерности с элементами для

которых выполняются условия:

Тогда элементы матрицы (где умно-

жение определено как поэлементная конкатенация множеств пар слов) удовлетворяют условию:

и ,={(р.ч) •• Р е1Г,-}Г2 & &Л(*1>Р)=Я}.

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

Метод построения циклов графа Ор.. Исходные данные: конечный детерминированный автомат

А = (8, X, у; 8, Л) . входное

слово , где

1 этап. Для входного слова р определяются матрицы переходов Мх для всех х , имеющих вхождение в слово р . Вычисляется матрица

2этап. Вычисляется матрица . Полагается и в матрице элементы

заменяются одним символом (для сокращения записей элементов).

3 этап. Анализируется матрица ©р(Ма) , строятся и анализируются степени матрицы по правилу: элементы главной диагонали матрицы (0р(Ма)) ', где 1 — 1,2, ... Iq , где < П - 1, отличные от пустых и пустые в предыдущих степенях матрицы (при I ¿2 ) , определяют петли ( 1-1 ) и циклы графа Gp .

В четвертой главе диссертации разрабатывается метод зацикливания, в котором получили развитие основные положения, изложенные в предыдущих главах. В качестве распознаваемых автоматов рассматриваются автоматы с nt двоичными задержками (2"| состояниями) , множеством входных сигналов и множеством выходных сигналов, то есть, автоматы вида А= ((^2) >(^2) (^2) ^ • S, X.). Функции 8иХ оказываются представленными соответственно наборами функций алгебры логики, каждая из которых зависит от двоичных переменных.

Задача распознавания автомата, без потери общности, ограничивается распознаванием автомата в паре автоматов (Ар AJ. Для этого автоматы представляются наборами функций (fit, fn. ■. .full) И (hji, ha, ... hrfi) , i= 1,2, и исследуются условия неравенства функций. Анализируемые функции gL и g2 заменяются их совершенными дизъюнктивными нормальными формами, в которыхзнаки « V» заменяются знаками « Ф » (сложения по

Г I I I

mod 2). Суммы конституэнт единицы g И g^ совмещаются в сумму g^ ® g^ . Каждая

конституэнта, входящая в сумму g^ © g^, является конституэнтой в СДНФ только для

одной из функций g1 или g2 (лемма 3)

Лемма 3. Пусть g1 и g2 - функции алгебры логики, зависящие (существенно или

несущественно) от одних и тех же переменных. Тогда множество { g^i Ф g^} состоит из тех и только тех конституэнт единицы, которые являются конституэнтами только для одной из функций g1 и g2.

В параграфе 4.2 разрабатывается представление процессов зацикливания изменений состояний с учетом того, что входные сигналы и состояния автомата совмещенно представлены конституэнтами единицы в множестве { © /jj}. Указываются правила построения графа, определяющего зацикливание, то есть, циклы и деревья, исключаемые при эксперименте с зацикливанием изменений состояний.

Основные положения иллюстрируются теоретическим примером для конкретного автомата. В теореме 17 содержится представление суммы f^ Ф ffa формулой, аналогичной формуле разложения функций по переменным в логическом базисе

Теорема 17. Для любых функций алгебры логики выпол-

няется равенство

hE, (х,,х2.....х„) © (xl.x2,...,xn)=® xf&x?>&...&x*'&.

(а,,а2,...,а„) е(Е$п

&(f,(o,,o2,...,an) 8 f,(cт,,а2.....а„),

где hZj (xj , Х2 , . . . , Х„) - сумма по mod 2 конституант единицы функции f i=1, 2.

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

выдаваемых разными автоматами при обходах одного и того же или разных циклов. В первом достаточном условии (теорема 18) основными свойствами являются: существование в

множестве { Ф $ } цилиндрического (по координатам, соответствующим кодам состояний) подмножества, зацикливание по единственному циклу, нечетная длина цикла.

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

Теорема 18. Пусть AJ , j — 1,2 , конечные детерминированные автоматы вида. Лу = ((-£;)"',,(Е2У3, 5 в непустом множестве конституэнт { к^ц ©

, существует цилиндрическое по последним , компонент подмножество

Рассматриваются возможные варианты обобщения теоремы 18.В теореме 19 содержится достаточное условие, в котором при зацикливании возможны изменения состояний в цикле из множества циклов. В условие включается новая характеристика: отношение числа единиц на выходе используемого выходного канала к длине цикла.

Теорема19. Пусть Aj , j = 1,2, конечные детерминированные автоматы вида

для которых выполняются условия:

1) в непустом множестве конституэнт единицы (для некоторого ¡0^ Пз ) существует цилиндрическое по последним п1 компонентам подмножество Ж;

2) (а,, а2,----<УН)

3) эксперименту с приложением периодической последовательности входных сигналов с периодом р— ((7/, С?2, . . ., <У„г ) соответствует возможное зацикливание по циклам

каждый из которых имеет нечетную длину

4) при изменении состояний автомата А, в цикле Ьу 1 <У< со, на ¡ц—М выходе автомата А, выдается точно а „ выходных сигналов 1.

Если для любых v, I, где уф1тя. 1 ¿V, 1< Ф, выполняется неравенство

то простым безусловным экспериментом с зацикливанием с периодом р распознается автомат в паре автоматов {А,, А).

Теорема 20 обобщает теоремы 18 и 19 на случай наблюдения выходных сигналов на всех выходных каналах автомата.

Теорема 20. Пусть А,, ] = 1,2, конечные детерминированные автоматы вида А} = ((£2У1 > (Ег )"', (Е2 У', 8 , Х] ) , для которых выполняются условия:

1) в непустом множестве конституэнт единицы ^ { А2// ® к^ц } существует цилиндрическое по последним п1 компонентам подмножество Ж;

3) эксперименту с приложением периодической последовательности входных сигналов с периодом р = (¿г/, О}, . . . , сП1) соответствует возможное зацикливание по со циклам

4) при изменении состояний автомата А, в цикле Ь„, V — 1, 2, ... , СО, на выходах автомата выдается точно а., наборов выходных сигналов, отличных от нулевого набора (0,0,.. .,0);

5) для любых У, I, 1 < V, 1^(0, выполняется неравенство

Тогда простым безусловным экспериментом с зацикливанием с периодом р распознается автомат в паре автоматов {А,, А).

На основании теорем 18-20 формулируется метод распознавания автомата с зацикливанием по периодическим последовательностям входных сигналов с однобуквенными периодами. Зацикливание по однобуквенным периодам обладает рядом преимуществ, среди которых «простота» построения циклов, автоматическое исключение промежуточных состояний между состояниями I в 5($,р), простая процедура исключения состояний, не входящих в циклы и т.п.

Исходные данные: Конечные детерминированные автоматы А1 и А2 вида

Средства распознавания: простой безусловный эксперимент (по Э. Муру и А. Гиллу) с приложением периодической последовательности с периодом - однобуквенным словом и наблюдением выходных сигналов при изменениях состояний в циклах.

1 шаг. Функциям выходов Л/ и сопоставляются наборы функций алгебры логики

(Ъц, й/2. • • ■ . ) и ¡122, ■ ■ ■ , ^гп,) и строится множество конституэнт единицы и. { ^п ® 1^21 }• Если это множество пусто, то метод не применим.

2 шаг. В (непустом) множестве { © А^,- } выделяется подмножество Ж>

цилиндрическое по последним п1 координатам. Если такого подмножества нет, то метод не применим.

3шаг. В рассматриваемом цилиндрическом подмножестве х выбирается элемент (о/, .. ., ) и для периода р = (оу, о>,..., 0„г) определяются циклы L\,Li,...,

и величины а/, 42, . ■ ■, Ою для автомата Аг

4 шаг. Для определенных на шаге 3 величин |, \Ь2 | , . . ., |£<и] и 01,02,.. •> ат проверяется условие

для всех уи I,, 1 £ V, 1 < СО ■ Если для выбранного периода/) это условие выпол-

</,+г

няется, то экспериментом с приложением последовательности р (¿1 - наибольшая длина путей в циклы, а г - наименьше общее кратное чисел |£.г |, . . ., ) и наблюдением г последних выходных сигналов автомат распознается в паре автоматов (А,, А).

Если для р условие не выполняется, то производится перебор цилиндрических подмножеств и их элементов в соответствии с шагами 2 и 3.

Если перебор по всем вариантам, определяемым шагами 2 и 3 не дает выполнения условия, указанного в шаге 4, то метод не применим.

В методе использованы достаточные условия, следовательно, невозможность применения метода к паре автоматов (А,, А2) не означает, что простым безусловным экспериментом автомат не распознается в паре (А,, А).

Заключение

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

1. Описана и обоснована классификация конечных детерминированных автоматов на основании учета специфических свойств комбинационных частей автоматов. Описаны свойства классов автоматов как свойства их комбинационных компонент.

2. Решена установочная задача для автоматов с зацикливанием. Для чего построена и исследована математическая модель процесса зацикливания автомата. Изучено функционирование автомата с изменениями состояний в циклах. Получены необходимое и достаточное условие существования решения установочной задачи в исследуемом классе автоматов (с зацикливанием).

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

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

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

Основные публикации.

1. Кунявская А.Н. Об одном подходе к классификации конечных автоматов по свойствам комбинационных компонент. Деп. в ВИНИТИ. 16.10. 2002 года. № 1763-В2002. 31 с.

2. Кунявская А.Н Решение установочных задач конечных автоматов экспериментом с зацикливанием состояний/ /Межвузовский сборник научных трудов. Теоретические проблемы информатики и ее приложений-Вып.5.- Саратов.-Изд-во Сарат. ун-та. 2002 г.

3. Сытник А.А., Креницкий А.П., Кунявская А.Н Об одном подходе к исследованию дискретных систем с изменяемым поведением./ /Межвузовский сборник научных трудов. Теоретические проблемы информатики и ее приложений - Вып.4.- Саратов.- Гос-УНЦ «Колледж».- 2001 г. С. 120-125.

4. Сытник А.А., Кунявская А.Н., Рзун ИГ. Об одном подходе к распознаванию автомата с изменениями состояний в циклах. / /Межвузовский сборник научных трудов. Теоретические проблемы информатики и ее приложений - Вьгп.5.- Саратов.- Изд-во Сарат. ун-та. 2002 г.

5. Сытник А.А., Шульга Т.Э., Кунявская А.Н. Анализ и синтез универсального автомата-перечислителя. //Тезисы докладов Международной конференции «Компьютерные науки и информационные технологии». Саратов. 2002 г.С. 70-71.

Подписано в печать 11.09.2004 г. Формат 60x84 1/16.Объем 1,0 усл. п. л. Тираж 100 экз. Бумага офсетная. Печать трафаретная. Заказ 104.

Типография «Саратовский источник» Лиц. ПД № 7-0014 от 29 мая 2000 г. г. Саратов, ул. Университетская, 42, оф. 22 тел.: 520-593

¡17 2 85

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Кунявская, Анна Наумовна

Введение.

Глава 1. Классификация конечных детерминированных автоматов и алгебра композиции автоматов

1.1. Классификация конечных автоматов по свойствам комбинационных частей.

1.2. Алгебра композиции автоматов.

1.3. Свойства классов автоматов, как свойства их комбинационных компонент.

Глава 2. Установочная задача для автоматов, метод распознавания автомата с зацикливанием изменений состояний

2.1. Необходимое и достаточное условие существования решения установочной задачи.

2.2. Функционирование автомата с изменениями состояний в циклах.

2.3. Математическая модель процесс зацикливания автомата.

Глава 3. Метод решения установочной задачи на основе изменений состояний в цикле

3.1. Матричный метод построения решения установочной задачи.

3.2. Теорема о связи решения установочной задачи для модели зацикливания автомата.

3.3. Метод построения циклов графа GP.

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

4.1. Множество конституэнт единицы комбинационной части автомата и пары автоматов.

4.2. Граф, определяющий совмещение конституэнт единицы в функциях переходов и выходов автоматов.

4.3. Достаточные условия для распознавания автоматов методом зацикливания.

Введение диссертация по математике, на тему "Распознавание конечных детерминированных автоматов методом зацикливания"

Практическое и теоретическое значение автоматных моделей в решении задач проектирования и технического диагностирования, познания процессов формирования и передачи сигналов в биологических системах, систематизации и оптимизации управляющих воздействий в экономике и т.д. стало причиной интенсивных исследований по теории автоматов. Разнообразие возникших задач, подходов к их решению, научных позиций исследователей привело к выделению классов автоматов (автоматы типов Мили и Мура, автоматы Медведева, автономные автоматы, автоматы с конечной глубиной памяти, (n, m, 1) - автоматы и т.д.), а также к разработке различных математических способов их задания (табличное задание, графы автоматов, автоматные матрицы, логические уравнения, формулы языка регулярных выражений, задание автомата композицией автоматов).

А = (S, X, Y, S, Я), где S, X и Y - соответственно множества состояний, входных и выходных сигналов, а 5 и А, функции переходов 5: S х X —> S и выходов Л: S х X —> S, заменялась структурной формой, то есть, композицией преобразователей сигналов и элементов памяти.

У= (s,x) = (s, х) s'eS

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

В качестве средства разделения множества состояний автомата на подмножества используется приложение периодических последовательностей входных сигналов. Как показано A.M. Богомоловым и В.А. Твердохлебовым в работе [11], в этом случае возникает циклическое изменение состояний. Состояния, не вошедшие в циклы, можно исключить из анализа и оставить для анализа только те состояния, которые вошли в циклы.

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

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

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

В первой главе диссертации расширяется классификация конечных детерминированных автоматов на основании учета специфических свойств комбинационных частей автоматов. Для этого рассматривается представление комбинационной части наборами функций алгебры логики ос = (fi, f2, . , fni) и Р = (hj, h2, . , hn3). Кодирование элементов множества состояний S двоичными векторами размерности п} , множества входных сигналов X двоичными векторами размерности п2 и множества выходных сигналов Y двоичными векторами размерности п3 позволяет представить комбинационную часть набором функции алгебры логики вида: fl fa, %2> ••■ j % п2 , Z}, Z2, ■■■ , Z„i) h} (xj, X2, . , x n2 , Z], z2, . , Zni)

Кз (Xl, X2, ■■■, X n2 , Z], z2, ■■■ , Zni)

Принимаемая классификация построена на классификации функций fi, 1 < i < П[, hj, 1 < j < п3, по их принадлежности классам Поста: К0 (функции сохраняющие 0), К} (функции сохраняющие 1), KL (линейные функции), Кт (монотонные функции), Ks (самодвойственные функции). В качестве памяти автомата рассматривается набор из П] элементов задержки сигнала на один такт. Здесь же рассматривается наличие сочетаний свойств, то есть принадлежность функций алгебры логики классам вида j Т т s > где а имеет значение а, если класс определяется наличием у функции свойства а, и значение а , если функции класса не имеют свойства а.

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

Задание конечного детерминированного автомата в виде трех множеств S, X, Y и двух функций 8 : S х X S , Л : S х X —> S удобно для теоретического рассмотрения законов функционирования автомата с использованием свойств функций и множеств. Такого представления автомата оказывается недостаточным для решения задач, связанных с анализом структуры технической (биологической, экономической, производственной и т.п.) системы, в качестве математической модели, которой используется автоматом.

Техническая система и, в частности, дискретные устройства управления (см. С.В. Яблонский [66], В.М. Глушков [26] ) создается на основе композиции элементов логического типа и элементов памяти. В первой главе диссертации приводятся правила правильной композиции элементов и новое, предлагаемое рассмотрение связей элемента с другими элементами в структуре автомата.

В качестве основных свойств положения отдельного элемента в структуре выбраны:

- управляемость входом элемента (вход элемента является внешним входным узлом автомата);

- наблюдаемость выхода элемента.

- операция изолированного раздвоения узла,

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

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

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

- теорема 10 о существовании точно одного в классе (2, 2, 2)-автоматов сильносвязного, самодвойственного и сохраняющего 0 автомата,

- теорема 11 о длине синхронизирующей последовательности для сильносвязного, самодвойственного и сохраняющего 0 автомата (из класса (2, 2, 2)-автоматов), теорема 12 о частном случае эквивалентности свойств сохранять О и сохранять 1.

В теореме 13 уточняется представление о процессе решения установочной задачи и разделяются два способа уменьшения множества распознаваемых состояний:

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

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

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

В параграфе 2.3 процесс зацикливания состояний формализуется и строится математическая модель процесса. Разработано представление процесса зацикливания конечным детерминированным автоматом, состояниями которого являются циклы (графа зацикливания по периодической входной последовательности вида рт , где р е X* и т е N1). В качестве макровходных сигналов, переводящие состояния из одних циклов в другие циклы. При этом допускается изменение периода (входного слова, используемого как период периодической последовательности входных сигналов) для зацикливания.

При изменении состояний в цикле рассматривается возможность наблюдения при изменении состояний в цикле:

- выходных сигналов вида Л (s, pri р) Л(д (s, pr, а р), pr\p\ р ), то есть, первого или последнего выходного сигнала для каждого периода р и состояния s, принадлежащего циклу;

- выходного слова Л (s, р) для каждого состояния s цикла и отдельного периода р,

- некоторых выходных сигналов слова Л (s, р).

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

- принадлежность всех состояний автомата циклам при зацикливании одной и той же компоненте связности,

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

- число состояний автомата, не принадлежащих циклам (число состояний в циклах), при зацикливании изменений состояний атвомата для заданной периодической последовательности входных сигналов,

- наличие циклов в виде петель (циклов длины 1) и циклов длины К.

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

Для того, чтобы распознавание автомата методом зацикливания сделать содержательно понятным, в параграфе 3.2 все основные формальные понятия и построения иллюстрируются на примере. Для этого задаются три автомата А] , А2 , и А3 , выбираются периоды р} , р2 и р3 и строятся математические модели процессов зацикливания. На рис. 18-26 приведены соответствующие графы, показан выбор наблюдаемых выходных последовательностей и рассмотрены функции переходов и выходов конечного детерминированного автомата, представляющего пределы зацикливания.

В параграфе 3.3 теоремами 15 и 16 систематизируется анализ законов функционирования автоматов с целью поиска периодических последовательностей входных сигналов. В основе систематизации действий лежит построение автоматных матриц и возведение матриц в степени. Теоремы обосновывают следующий факт: возведение матрицы в степени на основе конкатенации слов (замена умножения чисел) и теоретико-множественного объединения (замена сложения чисел), позволяет получать связи состояний и их р-преемников (теорема 15), а также наблюдаемые выходные слова (теорема 16). В этом же параграфе формулируется метод построения циклов для процесса зацикливания, базирующийся на построении автоматных матриц, возведении матриц в степени и анализе элементов степеней матриц.

В четвертой главе диссертации разрабатывается метод зацикливания, в котором получили развитие основные положения, изложенные в предыдущих главах. В качестве распознаваемых автоматов рассматриваются автоматы с nj двоичными задержками (2nl состояниями), множеством входных сигналов и множеством (Е2) "3 выходных сигналов, то есть, автоматы вида А = ((Е2) , (Е2) *2, (Е2) щ , 8, X ). Функции 8 и 1 оказываются представленными соответственно наборами (fh f2, . . . fnj) и (hj, h2, . . . hn3) функций алгебры логики, каждая из которых зависит от nl + п2 двоичных переменных.

Задача распознавания автомата, без потери общности, ограничивается распознаванием автомата в паре автоматов (A j , Л2). Для этого автоматы представляются наборами функций (fn.fn, ■ ■ - Ли) и (hn, h2i, . . . hn3i) , /= 1,2 , и исследуются условия неравенства функций. Анализируемые функции gi и g2 заменяются их совершенными дизъюнктивными нормальными формами, в которых знаки « V» заменяются знаками «©»

2 Г сложения по mod 2). Суммы конституэнт единицы g и g^ совмещаются в

I SI сумму gi © g . Каждая конституэнта, входящая в сумму g^ © g^, является конституэнтой В СДНФ ТОЛЬКО ДЛЯ ОДНОЙ ИЗ функций g; ИЛИ (лемма 3).

В параграфе 4.2 разрабатывается представление процессов зацикливания изменений состояний с учетом того, что входные сигналы и состояния автомата совмещенно представлены конституэнтами единицы в множестве {jf ® }. Указываются правила построения графа, определяющего зацикливание, то есть, циклы и деревья, исключаемые при эксперименте с зацикливанием изменений состояний.

Основные положения иллюстрируются примером для конкретного (заданного диаграммой Мура на рис. 30) автомата. В теореме 17 содержится представление суммы © формулой, аналогичной формуле разложения функций по переменным в логическом базисе < &,v, >.

В первом достаточном условии (теорема 18) основными свойствами являются:

- зацикливание по единственному циклу,

- нечетная длина цикла.

Рассматриваются возможные варианты обобщения теоремы 18. В теореме 19 содержится достаточное условие, в котором при зацикливании возможны изменения состояний в цикле из множества циклов. В условие включается новая характеристика: отношение числа единиц на выходе используемого выходного канала к длине цикла. Допускается любое конечное число нечетных по длине циклов.

Теорема 20 обобщает теоремы 18 и 19 на случай наблюдения выходных сигналов на всех выходных каналах автомата.

На основании теорем 18-20 формулируется метод распознавания автомата с зацикливанием по периодическим последовательностям входных сигналов с однобуквенными периодами. Зацикливание по однобуквенным периодам обладает рядом преимуществ, среди которых «простота» построения циклов, автоматическое исключение промежуточных состояний между состояниями s и 8 (s, р), простая процедура исключения состояний, не входящих в циклы и т.п.

Заключение диссертации по теме "Дискретная математика и математическая кибернетика"

Заключение

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

Основные публикации

2. Кунявская А.Н Решение установочных задач конечных автоматов экспериментом с зацикливанием состояний./ /Межвузовский сборник научных трудов. Теоретические проблемы информатики и ее приложений-Вып.5.- Саратов.-Изд-во Сарат. ун-та. 2002 г.

4. Сытник А.А., Кунявская А.Н., Рзун И.Г. Об одном подходе к распознаванию автомата с изменениями состояний в циклах. / /Межвузовский сборник научных трудов. Теоретические проблемы информатики и ее приложений - Вып.5.- Саратов.- Изд-во Сарат. ун-та. 2002 г.

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Кунявская, Анна Наумовна, Саратов

1. Автоматы. //Сборник статей под редакцией К.Шеннона. М. Иностранная литература. 1956. 403 с.

2. Айзерман М.А. и др. Логика. Автоматы. Алгоритмы. М. Физматгиз. 1963. 140 с.

3. Арбиб М. Алгебраическая теория автоматов, языков, полугрупп. М. Статистика. 1975. 335 с.

4. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М. Мир. 1978. 4.1. 612 с.

5. Баранов С.И. Цифровые устройства на программируемых БИС с матричной структурой. М. Радио и связь. 1986. 270 с.

6. Барздинь Я.М., Калниньш Я.Я. Универсальный автомат с переменной структурой. //Автоматика и вычислительная техника. 1974. N2. С.9-18.

7. Бахтурин Ю.А. Основные структуры современной алгебры. М. Наука. 1990.318 с.

8. Богомолов A.M., Сперанский Д.В. Аналитические методы в задачах конроля и анализа дискретных устройств. Саратов. Изд- во Сарат. унта. 1986. 240 с.

9. Богомолов A.M., Сытник А.А. Универсальные конечные автоматы. //Доклады АН СССР. 1987. Т. 294.N3. С. 525-528.

10. Богомолов С.А. О восстановлении автомата по экспериментам. //Дискретная математика. 1989. Т.1. Вып.1. С. 135-146.

11. П.Богомолов A.M., Твердохлебов В.А. Диагностика сложных систем. Киев. Наукова Думка. 1974. 128 с.

12. Богомолов A.M., Твердохлебов В.А. Целенаправленное поведение автоматов. Киев. Наукова Думка. 1975. 123 с.

13. Брауэр В. Введение в теорию конечных автоматов. М. Радио и связь. 1987. 392 с.

14. Буевич В.А. Построение универсальной о.-д. функции с двумя переменными. //Проблемы кибернетики. 1965. N 15. С. 249-252.

15. Бурбаки Н. Теория множеств. М. Мир. 1965. 455 с.

16. Бусленко Н.П. Моделирование сложных систем. М. Наука. 1978. 399 с.

17. Вагнер В.В. Теория полугрупп и ее приложения. Саратов. Изд-во Сарат. ун-та. 1965. С. 3-179.

18. Ван дер Варден Б.Л. Алгебра. М. Наука. 1979. 623 с.

19. Варшавский В.И. Коллективное поведение автоматов. М. Наука. 1973. 407 с.

20. Варшавский В.И. Апериодические автоматы. М.Наука. 1976. 424 с.

21. Гаврилов М.А., Девятков В.В., Пупырев Е.И. Логическое проектирование дискретных автоматов. М. Наука. 1977. 352 с.

22. Геллер С.И., Журавлев Ю.И. Основы логического проектирования цифровых вычислительных машин. М. Сов. радио. 1969 272 с.

23. Гилл А. Введение в теорию конечных автоматов. М. Наука. 1966. 272 с.

24. Гороховский С.С., Рысцов И.К. Об изоморфизме графов отображений. //Кибернетика. 1982. N 6. С. 45-52.

25. Горяшко А.П. Логические схемы и реальные ограничения. М. Энергоиздат. 1982. 184 с.

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

27. Глушков В.М. Абстрактная теория автоматов. //Успехи мат.наук. 1961. Т. 14. Вып. 5. С. 3-62.

28. Глушков В.М., Капитонова Ю. В., Летичевский А.А. Теоретические основы проектирования дискретных систем. //Кибернетика. 1977. N 6. С. 5-20.

29. Глушков В.Г., Цейтлин Г.Е., Ющенко Е.Л. Алгебра, язаки, программирование. Киев. Наукова Думка. 1974. 328 с.

30. Горбатов В.А. Основы дискретной математики. М. Высшая школа. 1986.311 с.

31. Дроздов Е.А. Оптимизация структур цифровых автоматов. М. Сов. радио. 1975. 352 с.

32. Евреинов Э.В., Прангишвили И.В. Цифровые автоматы с настраиваемой структурой. М. Энергия. 1974. 240 с.

33. Заде JI. Общая теория систем. М. Мир. 1966.

34. Закревский А.Д. Алгоритмы синтеза дискретных автоматов. М. Наука. 1971.512 с.

35. Зыков А.А. Основы теории графов. М. Наука. 1987. 381 с.

36. Капитонова Ю.В. Об изоморфизме абстрактных автоматов. //Кибернетика. 1965. N 4,5.

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

38. Кратко М.И. Алгоритмическая неразрешимость проблемы полноты для конечных автоматов. //Доклады АН СССР. 1964. Т. 155. N 1. С. 35-37.

39. Кунявская А.Н. Об одном подходе к классификации конечных автоматов по свойствам комбинационных компонент. Деп. в ВИНИТИ. 16.10. 2002 года. № 1763-В2002. 31 с.

40. Кунявская А.Н Решение установочных задач конечных автоматов экспериментом с зацикливанием состояний. / /Межвузовский сборник научных трудов. Теоретические проблемы информатики и ее приложений Вып.5.- Саратов.- Изд-во Сарат ун-та. 2002 г.

41. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. М. Наука. 1985. 319 с.

42. Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов. М. Энергоатомиздат. 1989. 328 с.

43. Мелихов А.Н. и др. Применение графов для проектирования дискретных устройств. М. Наука. 1974. 294 с.

44. Месарович М., Такахара Я. Общая теория систем: математические основы. М. Мир. 1978. 256 с.

45. Многофункциональные автоматы и элементная база цифровых ЭВМ.//Под ред. В.А. Мищенко. М. Радио и связь. 1981. 240 с.

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

47. Пархоменко П.П. О технической диагностике. М. Знание. 1969. 64 с.

48. Пикар С. О базисах симметрической группы.//Кибернетический сборник. 1965. Вып. 1. с. 7- 34.

49. Поспелов Д.А. Логические методы анализа и синтеза схем. М. Энергия. 1974. 368 с.

50. Сытник А.А. Перечислимость при восстановлении поведения автоматов. //Доклады РАН N 328 N 1.1993.

51. Сытник А.А. Восстановление поведения сложных систем. Саратов. Изд- во Сарат. ун-та. 1992. 192 с.

52. Сытник А.А. Методы и модели восстановления поведения автоматов. //Автоматика и телемеханика. 1992. N11.

53. Сытник А.А., Кунявская А.Н., Рзун И.Г. Об одном подходе к распознаванию автомата с изменениями состояний в циклах. / /Межвузовский сборник научных трудов. Теоретические проблемы информатики и ее приложений Вып.5.- Саратов.- Изд-во Сарат ун-та.2002 г.

54. Сытник А.А., Шульга Т.Э., Кунявская А.Н. Анализ и синтез универсального автомата-перечислителя. //Тезисы докладов Международной конференции «Компьютерные науки и информационные технологии». Саратов. 2002 г.С. 70-71.

55. Твердохлебов В.А. Логические эксперименты с автоматами. Саратов. Изд- во Сарат. ун- та. 1988. 184.Трахтенброт Б.А., Барздинь Я.М. Конечные автоматы. Поведение и синтез. М. Наука. 1970. 400 с.

56. Ульман Дж. Вычислительные аспекты СБИС. М. Радио и связь. 1990. 480 с.

57. Ушаков И.А. Построение высоконадежных систем. М. Энергия. 1974. 64 с.

58. Феррари Д. Оценка производительности вычислительных систем. М. Мир. 1981. 376 с.

59. Фридман А., Меннон П. Теория и проектирование переключательных схем. М. Мир. 1978. 580 с.

60. Харари Ф. Теория графов. М. Мир. 1973. 300 с.

61. Цетлин М.Л. Исследования по теории автоматов и моделированию биологических объектов. М. Наука. 1969. 317 с.

62. Цифровая вычислительная техника. //Под ред. Э.В. Евреинова. М. Радио и связь. 1991. 464 с.

63. Цыпкин Я.З. Адаптация и обучение в автоматических системах. М. Наука. 1968. 399 с.

64. Яблонский С.В. Введение в дискретную математику. М. Наука. 1979. 272 с.

65. Якубайтис Э.А. Логические автоматы и микромодули. Рига. Зинатне. 1975. 260 с.