Эквивалентность автоматов

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

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

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

, , и .

Эквивалентность функций выходов автоматов определяется так: если для автомата Мура имеем функции переходов и его функция выходов , то и в автомате Мили функция выходов должна формировать выходной сигнал .

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

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

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

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

В соответствии с приведенным правилом и используя таблицу 3.11, запишем множество пар «состояние-выход» для автомата Мура и пронумеруем те пары, которые порождены каждым состоянием автомата Мили: ; ; .

С каждым состоянием автомата Мура связывают выходной сигнал , который является вторым элементом пары. Тогда

; ; .

Учитывая эти обозначения, получаем таблицу 3.12, получаем обозначенную таблицу переходов и выходов эквивалентного автомата Мура.

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

Дата добавления: 2015-07-08