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

• Автор: Кунявская, Анна Наумовна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Саратов
• Количество страниц: 143 с.

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

А = (Б, X, ¥, 8, Л),

где 8, X и У - соответственно множества состояний, входных и выходных сигналов, а 5 и А, функции переходов 8: Б я- X -> Б и выходов Л: Б х X —> Б, заменялась структурной формой, то есть, композицией преобразователей сигналов и элементов памяти.
Первое, принципиально важное, представление абстрактного автомата на пути к его структурному заданию, определяется следующей схемой:
х е X V е У

-° у = (я, х)

в' = (б, х)
б' е Б
Структурная декомпозиция абстрактного автомата осуществляется на основе синтеза комбинационной части как суперпозиции функций алгебры логики и реализации памяти элементами задержки сигналов. Структурная форма задания конечных детерминированных автоматов принципиально повысила эффективность приложений теории автоматов и представила новые возможности для теоретических исследований. В частности, в диссертации декомпозиция автомата на комбинационную часть и память используется с целью применения развитого математического аппарата алгебры логики.
В диссертации исследуется проблема, как можно судить по анализу специальной литературы, впервые ставшая предметом систематического рассмотрения в теории автоматов: разделение множества состояний автомата на два подмножества - подмножество состояний, анализ которых можно исключить, и подмножество состояний, на которых ограниченные функции переходов и выходов автомата сохраняют специфику функционирования. Распознавание автоматов базируется на этой специфике изменений состояний и соответствующих выходных последовательностей.
В качестве средства разделения множества состояний автомата на подмножества используется приложение периодических
последовательностей входных сигналов. Как показано А.М. Богомоловым и
В.А. Твердохлебовым в работе [11], в этом случае возникает циклическое изменение состояний. Состояния, не вошедшие в циклы, можно исключить

Комбинац. часть
р»
яе в
ПАМЯТЬ
сведение задачи к установочной задаче для расщепляемого (по терминологии А.Гилла [23 ]) автомата
А =( ) (8)
16/ »е/ 1€
В случае, когда множеств состояний £ = расщепляемого автомата $
/е
велико, практическое решение задачи распознавания (например, при техническом диагностировании на основе распознавания автоматов) оказывается невозможным. При сохранении основных идей, на которых построено сведение задачи, можно распознавать конечный детерминированный автомат приближенно с сокращением числа анализируемых состояний представленный конечным
недетерминированным автоматом. На принципиальную возможность разработки такого метода указано в работе А.М. Богомолова, В.А. Твердохлебова [11].
Пусть А = (Б, X, У, 6, И) - конечный детерминированный автомат. Как показано в работе [11], для любого входного слова р € X связи состояний из множества состояний 5, представленные состояниями и их р - преемниками, определяются графом со свойствами:
- граф имеет конечное число связных подграфов;
- каждый подграф обязательно имеет один цикл (или петлю), каждая вершина которого может быть корнем дерева:
- граф ориентированный с направлением дуг от висячих вершин деревьев к их корням с обходом контуров.
Основная идея сокращения числа состояний автомата, требующих анализа при распознавании, состоит в исключении из анализа всех вершин деревьев, кроме корней деревьев. Корни деревьев образуют циклы или петли. Следовательно, в предлагаемом методе распознавания анализируется наблюдаемое поведение автомата, представленное циклами