Еквівалентні автоматы

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

Эквивалентные автоматы Автомат Мили S1 установлен в исходное состояние a1. На вход подается входное слово: В результате сформировано выходное слово:

Эквивалентные автоматы Автомат Мура S2 установлен в исходное состояние a1. На вход подается входное слово: В результате сформировано выходное слово:

Эквивалентные автоматы Два автомата S1 и S2 называются эквивалентными, если: входной и выходной алфавиты совпадают; их реакции из исходного состояния на любое входное слово совпадают; Автомат Мили S1 Автомат Мура S2 Существует теорема: для любого автомата Мура существует эквивалентный ему автомат Мили и наоборот.

Преобразование автоматов Мура в Мили При табличном задании таблица переходов автомата Мили совпадает с таблицей переходов автомата Мура. Таблица выходов автомата Мили получается из таблицы переходов заменой символа A s, стоящего на пересечении строки z f и столбца A m, на символ w g, отмечающий столбец A s в совмещенной таблице автомата Мура. Пусть задан автомат Мура: Таблица переходов эквивалентного автомата Мили совпадает с таблицей автомата Мура: Считается, что на переходе из состояния A m в состояние A s в эквивалентном автомате Мили должен быть сформирован такой же выходной сигнал, что и в автомате Мура, после того как автомат перешел в состояние A s. Таблица выходов автомата Мили

Преобразование автоматов Мура в Мили При графическом задании автомата Мура переход к автомату Мили выполняется следующим образом: выходной сигнал w g, формируемый в состоянии A s, переносится на все дуги, входящие в эту вершину.

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

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

Преобразование автоматов Мили в Мура Автомат Мили Эквивалентный автомат Мура