Эквивалентность автоматов Мили и Мура
Существует 2 варианта перехода от Автомата Мили к автомату Мура – общий и тривиальный.
Пример. Задан автомат A5 Мили в виде графа. Построить совмещенную таблицу переходов/выходов. Найти эквивалентный ему автомат Мура, построить граф и отмеченную таблицу переходов.
Решение.
Совмещенная таблица переходов/выходов.
| S0 | S1 | S2 | S 3 | |
| X 1 | S1 Y1 | S0 Y2 | S1 Y1 | S0 Y1 |
| X 2 | S2 Y2 | S2 Y2 | S3 Y1 | S1 Y2 |
Нахождение эквивалентного автомата Мура.
1. Определение в таблице одинаковых переходов/выходов и пометка их .
| S0 | S1 | S2 | S 3 | |
| X 1 | S1 Y1 | S0 Y2 | S1 Y1 | S0 Y1 |
| q3 | q 2 | q3 | q 1 | |
| X 2 | S2 Y2 | S2 Y2 | S3 Y1 | S1 Y2 |
| q5 | q5 | q6 | q4 |
Пометка начинается с анализа состояния S0 и выходной реакции Y1 . Если такая комбинация S0/Y1 встречается в таблице, то ей приписывается пометка q 1 Если рассматриваемая комбинация встречается несколько раз, то всем приписывается одинаковая пометка. Далее анализируется наличие комбинации S0/Y2 , если она встречается, то ей приписывается пометка q 2 , и так далее рассматривается наличие всех комбинаций <состояние>/<буква вых. алфавита> и всем приписываются пометки.
2. Запись множеств эквивалентных состояний
Каждому исходному состоянию приписывается множество соответствующих им пометок (рассматривается построенная таблица с пометками). Ищется в таблице очередное исходное состояние и в соответствующее множество записывается приписанная ему пометка. Для начального состояния S0 в множество пометок добавляется также q 0 - для идентификации начального состояния автомата Мура.
|
|
|
Для рассматриваемого примера получены следующие множества эквивалентных состояний .
3. Построение отмеченной таблицы переходов автомата Мура в соответствии с п.1 и 2.
| - | Y 2 | Y 1 | Y 1 | Y2 | Y 2 | Y 1 | |
| q0 | q1 | q2 | q3 | q4 | q 5 | q 6 | |
| X 1 | q3 | q3 | q3 | q2 | q2 | q3 | q1 |
| X 2 | q5 | q5 | q5 | q5 | q5 | q6 | q4 |
Общее количество состояний искомого эквивалентного автомата Мура = суммарному количеству проставленных пометок + метка начального состояния q 0, т.е. сумме количества элементов всех построенных эквивалентных множеств. В данном случае множество состояний автомата Мура будет следующим: 
.
Выходные реакции записываются следующим образом: в таблице с пометками ищется пометка, соответствующая рассматриваемому состоянию автомата Мура и в отмеченную таблицу автомата Мура записывается находящаяся в найденной ячейке выходная реакция.
Запись переходов: рассматриваются множества эквивалентных состояний и в столбцы таблицы автомата Мура, соответствующие элементам рассматриваемого множества, записываются проставленные пометки из столбца соответствующего эквивалентного состояния автомата Мили, например, в столбцы состояний q 0 q 1 q 2 автомата Мура будут записаны пометки q 3 q 5 из столбца S0 таблицы автомата Мили.
|
|
|
4. По построенной отмеченной таблице переходов автомата Мура можно построить графовое представление автомата Мура, эквивалентного заданному автомату Мили.
Пример. Задан автомат A6 Мура в виде графа. Построить отмеченную таблицу переходов. Найти эквивалентный ему автомат Мили, построить граф и совмещенную таблицу переходов/выходов.
Решение
Автомат Мили имеет столько же состояний, сколько у исходного автомата Мура. Переход от автомата Мура к эквивалентному автомату Мили заключается в том, что выходные реакции переносятся с вершин графа на ребра, входящие в данные вершины.
Пример. Интуитивно построить автомат Мура в табличном и графовом виде, выполняющий подсчет четности единиц (1) во входном слове.
Решение.
На вход поступают согласно условию 0 и 1, следовательно входной алфавит X={0,1}. На выходе может быть 2 варианта сигналов: - число единиц четное; - число единиц нечетное. Следовательно выходной алфавит Y={чет, нечет}.
|
|
|
По условию требуется построить автомат Мура, значит обязательно должно существовать начальное состояние q0, с неопределенной выходной реакцией. Также потребуется еще 2 состояния для сигналов – четности числа единиц и их нечетности, соответственно – состояния q1 и q2. Тогда множество состояний q={q0, q1, q2}.
На вход автомата могу поступать 0 или 1, значит из начального состояния может быть 2 перехода – один по 0, а другой по 1. Если в начальный момент времени на вход поступает 0, то количество 1 четное, переход осуществляется в состояние q1, если поступает 1, то количество 1 нечетное и осуществляется переход в состояние q2. В дальнейшем поступление 0 на вход не изменяет сигнала о четности/нечетности числа 1, т.е. состояние автомата не изменяется, поступление на вход 1 изменяет состояние автомата.
Граф автомата Мура.
Отмеченная таблица переходов.
| - | чет | нечет | |
| q0 | q1 | q2 | |
| 0 | q1 | q1 | q2 |
| 1 | q2 | q2 | q1 |
Дата добавления: 2019-02-22; просмотров: 938; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!