Алгебраические свойства асинхронных автоматов

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

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. Подавтоматы асинхронных автоматов .
§1,1. Основные понятия и вспомогательные конструкции . .
§ 1.2. Подавтоматы асинхронных автоматов с двумя входными
сигналами
§1.3. Дистрибутивные решетки как решетки подавтоматов асинхронных автоматов
ГЛАВА 2. Конгруэнции асинхронных автоматов
§2.1. Асинхронные конгруэнции автоматов
§2.2. Конгруэнции асинхронных автоматов
ГЛАВА 3. Эндоморфизмы и автоморфизмы асинхронных автоматов
§3.1. Моноиды эндоморфизмов асинхронных автоматов . .
§3.2. Группы автоморфизмов асинхронных автоматов . . .
ЛИТЕРАТУРА
Введение
Предлагаемая работа посвящена изучению алгебраических свойств асинхронных автоматов, введенных в рассмотрение Кузнецовым О.П. [28] в 1965 году.
Конечным детерминированным автоматом с выходом называется пятерка А = (Б, X, У, 5, X), где Б, X, У — произвольные конечные непустые множества, называемые соответственно множеством состояний, множеством входных сигналов и множеством выходных сигналов автомата, отображение 6: Б х X —»Б называется функцией переходов автомата, а отображение Я: 8 х X —> У — функцией выходов.
Автомат, как один из важных видов управляющих систем, является математической моделью функционирования устройства с конечной памятью, преобразующего дискретную информацию.
Автомат А функционирует в дискретной временной шкале по следующему правилу [5]: если я е 8 — состояние автомата А в данный момент и на его вход подан сигнал х е X, то в следующий момент времени автомат перейдет в состояние 8(э, х) и выдаст на выходе сигнал Х(в, х).
Если функция переходов и функция выходов автомата определены для всех пар из Б х X, то автомат А называется всюду определенным, в противном случае автомат А называется частичным [14].
Конечным детерминированным автоматом без выхода называется тройка А = (8, X, 5), где 8, X и 8 несут тот же смысл, что и в автомате с выходом.
В настоящей работе будут рассматриваться только всюду определенные конечные детерминированные автоматы без выхода, которые далее называются просто автоматами.
Теория автоматов — развитая математическая теория с достаточно широкой тематикой задач. К настоящему времени в ней отчетливо

наметились (см. [38]) два аспекта: комбинаторный аспект и алгебраическая теория. Комбинаторный аспект теории автоматов в большей степени связан с поведением, анализом и синтезом автоматов. Этот подход нашел отражение в книгах В.М. Глушкова [15], В.Б. Кудрявцева, С.В. Алешина и
A.C. Подколзина [27], Брауэра [10] и др. Алгебраической теории автоматов посвящены работы А.М. Богомолова и В.Н. Салия [5], Г.М. Бродского [11], Б.И. Плоткина, Л.Я. Гринглаз и A.A. Гварамия [38], Арбиба[1] и др. Комбинаторный и алгебраический аспекты теории автоматов тесно взаимосвязаны. Абстрактно - алгебраические методы находят важные применения в теории языков [31] и алгоритмов (см. работы
B.М. Глушкова [14], [15]), в теории декомпозиции автоматов (статьи на эту тему имеются в[1]). В книге М.А. Спивака [44] алгебраические и комбинаторные вопросы теории автоматов исследуются на базе алгебраической теории бинарных отношений.
Автомат А = (S, X, б) называется автономным, если X является одноэлементным множеством: Х={х). В дальнейшем автономные
автоматы будем записывать в виде А = (S, 5) и рассматривать б как отображение множества S в себя, то есть 5: S —> S. Пусть А = (S, X, S) — некоторый автомат. Для фиксированного входного сигнала х е X определим функцию 6Х на множестве S так, что 8Х: s —> б (s, х). Автономные автоматы Ах = (S, бх), х g X, называются автономными компонентами автомата А.
При алгебраическом подходе автомат в первую очередь рассматривается как алгебраическая структура и становится объектом алгебраической теории. При этом автомат А = (S, X, б) трактуется как конечная унарная алгебра вида А = (S, (5Х | х е X}). Как отмечает
В.Н. Салий [40]: представление об автомате без выхода как о конечной унарной алгебре позволяет применить в теории автоматов хорошо разработанные универсально - алгебраические средства, придать установленным с их помощью фактам естественную автоматную трактовку.

Теорема 1.2.5. Подавтомат А* = (Э*, {хі, х2}, б) асинхронного автомата А = (8, {хі,х2},5) с двумя входными сигналами тогда и только тогда является дуальным атомом решетки подавтоматов 8иЬА, когда дополнение 8* подмножества Б* в 8 представляет собой изолированный асинхронный цикл четной длины, изолированную петлю или недостижимое состояние.
Доказательство.
Пусть А* будет дуальным атомом решетки 8иЪА. Если подмножество одноэлементное, то, очевидно, образующее его состояние является недостижимым. Предположим, что Э * имеет по крайней мере два элемента. Покажем, что число состояний в Б* четно и они образуют асинхронный цикл четной длины. Заметим, что, если Б* не одноэлементное подмножество в в, то для его элементов выполнено соотношение:
(Уя, г є в *)(3р, р є X*) 8(я, р) = X и 5(1, р) = я.
Предположим противное, то есть, что найдутся такие є 8*, что I не достижимо из з, то есть 1 € Э*. Поскольку А*— максимальный собственный подавтомат автомата А, то Э = 8* II 8(з). Имеем 1: й Б* и £ 8. Следовательно, I £ 8. что невозможно.
Заметим, что подмножество 8* является устойчивым в автомате А. Действительно, в силу взаимной достижимости состояний из этого подмножества и асинхронности автомата А, получаем, что в каждой вершине из этого подмножества присутствует петля по одному сигналу, а по второму сигналу происходит переход в другую вершину из этого же множества. Таким образом, подмножество 8* является устойчивым, а порожденный им подавтомат автомата А является сильно связным. По теореме 1.2.2 получаем, что дополнение 8* подмножества в* в 8 представляет собой изолированный асинхронный цикл четной длины.
Обратно, пусть А* = (8*, X, 8) — подавтомат автомата А и 8* удовлетворяет условию теоремы. Тогда Э является единственным, отличным