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

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

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

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

 

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

 

 

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

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

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

, , , ,

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

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

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

Пример:

 

 

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

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

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

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

 








Дата добавления: 2015-08-11; просмотров: 997;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.003 сек.