Тема 2.4. Эквивалентные автоматы, преобразования автоматов.

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

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

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

Преобразование автомата Мура в автомат Мили

Дан автомат Мура :

Построим автомат Мили :

При этом возьмем:

, , , ,

Осталось определить функцию .

Если в автомате Мура и , то в автомате Мили возьмем .

Это значит, что выходной сигнал переносится на все дуги, входящие в вершину .

Пример:

При табличном способе задания автоматов

- таблица переходов совпадает с таблицей переходов ;

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

Из самого способа построения автомата Мили очевидно, что он эквивалентен автомату Мура .