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

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

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

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

Во второй главе диссертации рассматривается установочная задача для автомата, условие существования ее решения и сведение задачи распознавания автомата к установочной задаче. Основные результаты получены Э. Муром [1 ] иА. Гиллом [23].

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

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

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

Основное содержание второй главы диссертации составляет изложение основных положений метода распознавания автомата (в заданном семействе автоматов), базирующихся на приложении периодической последовательности выходных сигналов. В работе A.M. Богомолова и В. А. Твердохлебова ([11], теорема 23) показано, что функционирование конечного детерминированного автомата под воздействием периодической входной последовательности с любым периодом р е X и рассмотрением связей состояний s и 8 (s, р), s е S, определяется конечным графом с циклами и деревьями, корни которых являются вершинами циклов.

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

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

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

— выходных сигналов вида Л (s, pri р) Л (д (s, pr, а р), prp р), то есть, первого или последнего выходного сигнала для каждого периода р и состояния 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» заменяются знаками «(c)».

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

.

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

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.