§2. Покрытие и эквивалентность. Морфизмы.

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

Пример. Автомат задан диаграммой:

Пусть входная строка и начальное состояние, тогда_, .

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

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

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

.

Определение 2: Автомат, который нельзя покрыть меньшим автоматом, называется минимальным. Будем писать: , еслипокрывает.

Теорема 1: Отношение покрытий рефлексивно и транзитивно.

Доказательство очевидно.

Определение 3: Автоматы иназываютсяэквивалентными, если автомат покрываети автоматпокрывает. В этом случае пишут:.

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

Следствие: Отношение эквивалентности автоматов рефлексивно, транзитивно и симметрично.

Пусть и– автоматы с общими входными и выходными алфавитами.

Определение 4: Морфизмом называется такое отображение , чтоии. Еслисюрьективно, то морфизм называетсяэпиморфизмом. Если - биекция, то морфизм называетсяизоморфизмом.

Теорема 2: Пусть эпиморфизм автоматана. Тогда для любой входной строкии любого начального состояниявходная строкаавтоматасовпадает с входной строкой автомата, если начальное состояниеравно.

Доказательство: Доказательство можно провести индукцией по числу с индуктивным шагом:

;

.

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

Пример. Автоматы, представленные следующими ориентированными графами, изоморфны.

§3. Эквивалентные состояния автоматов.

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

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

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

Заметим, что и– действительно отношение эквивалентности. Классы эквивалентности относительно, являются множествами всех пар состояний, перерабатывающих каждый входной символ в фиксированный выходной символ. Это означает, что. Обозначим черезотношения эквивалентности(т.е. множество всех пар эквивалентных состояний). Обозначим черездополнение к, т.е..

Пусть, например, даны таблицы состояний автоматов и:

Текущее состояние	ν 0 1	ξ 0 1
S0 S1 S2	S2 S1 S0 S2 S0 S1	0 1 1 0 0 1

Текущее состояние	 0 1	 0 1
S0 S1	S0 S1 S0 S0	0 1 1 0

G (E₁) = {(S₀, S₂), (S₂, S₀), (S₀, S₀), (S₁, S₁), (S₂, S₂)},

G (E₁) = {(S₀, S₁), (S₁, S₀), (S₁, S₂), (S_2, S₁)}.

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

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

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

Теорема 1: Если , то либо, либо для подходящей строкиимеем .

Доказательство: Утверждение означает, чтодля подходящей строки. При необходимости мы можем укоротить входную строку так, чтобы входные строки, отвечающиеи, отличались только последними символами. Пусть это уже сделано. Если после этого, то. Если же, то. Нопри условии. Таким образом, последние выходные символы автомата, считавшего, различны, если он исходил из начальных состоянийисоответственно. Чтобы выходы отличались, то естьдолжно быть выполнено условие:. Иначе последний входной символдаст один и тот же символ на выходе.

Теорема 2: Если , нодля всех, тодля подходящего элемента .

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

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

Доказательство: Доказательство теоремы проводится непосредственно. Если пара лежит в, то она лежит в. Значит нужно рассмотреть лишь такие пары, что для некоторой строкиимеем, а для всех строкимеем. Но в точности те пары, которые переводятся в,-м входным символоми стало быть, в, некоторым символом.

Лемма: Если , тодля всех.

Действительно, дальнейшие шаги не добавят новых пар состояний, т.к. согласно теореме 2, дополнение состоит из тех пар, которые переводятся подходящим символомв дополнение.

Пример: Пусть задана таблица состояний некоторого автомата.

Текущее состояние	След. состояние 0 1	Выход 0 1
S1	S1 S2	1 0
S2	S1 S3	1 0
S3	S5 S1	1 0
S4	S4 S2	1 0
S5	S4 S3	1 1

Для этого автомата .

Иными словами: . Первое разбиение на классы эквивалентности:,. Вход 0 переводит в состояние , в:,. Поэтому вход01 дает Следующие результаты:

и.

Отсюда и . Аналогично: и , так что имеет место условие:

.

Далее, входной символ 1 переводит состояние в , апереводит в состояние. Другими словами:и. Поэтому, т.к.и. Аналогично: , откуда следует:

.

Таким образом, разбиваетна классы эквивалентности:

,,,.

Дальнейший перебор показывает, что . Таким образом,и, а остальные пары состояний неэквивалентны.