Автоматы Мура и Мили — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Табличный способ задания автомата Мура)
м (rollbackEdits.php mass rollback)
 
(не показаны 142 промежуточные версии 5 участников)
Строка 1: Строка 1:
== Абстрактные автоматы ==
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Абстрактный автомат''' (АА) является математической моделью дискретного устройства и описывается шестикомпонентным набором <tex>S=(A, Z, W, \delta, \lambda, a_{1})</tex>, где
+
'''Абстрактный автомат''' (англ. ''Abstract Machine'') является математической моделью дискретного устройства и описывается шестикомпонентным набором <tex>S=(A, Z, W, \delta, \lambda, a_{1})</tex>, где
  
1. <tex>A=\{a_{1}, ..., a_{m}, ..., a_{M}\}</tex> - множество состояний.
+
* <tex>A=\{a_{1}, \dots, a_{m}, \dots, a_{M}\}</tex> {{---}} множество состояний.
  
2. <tex>Z=\{z_{1}, ..., z_{f}, ..., z_{F}\}</tex> - множество входных сигналов.
+
* <tex>Z=\{z_{1}, \dots, z_{f}, \dots, z_{F}\}</tex> {{---}} множество входных сигналов.
  
3. <tex>W=\{w_{1}, ..., w_{g}, ..., w_{G}\}</tex> - множество выходных сигналов.
+
* <tex>W=\{w_{1}, \dots, w_{g}, \dots, w_{G}\}</tex> {{---}} множество выходных сигналов.
  
4. <tex>\delta</tex> - функция переходов АА, которая некоторым парам \<состояние - входной сигнал\> (<tex>a_{m}</tex>, <tex>z_{f}</tex>) ставит в соответствие состояние АА <tex>a_{s}</tex>, т.е. <tex>a_{s} = δ(a_{m}, z_{f})</tex>, <tex>a_{s}\in A</tex>.
+
* <tex>\delta</tex> {{---}} функция переходов АА, которая некоторым парам состояние {{---}} входной сигнал <tex>(a_{m}</tex>, <tex>z_{f})</tex> ставит в соответствие состояние АА <tex>a_{s}</tex>, т.е. <tex>a_{s} = δ(a_{m}, z_{f})</tex>, <tex>a_{s}\in A</tex>.
  
5. <tex>\lambda</tex> - функция выходов АА, которая некоторым парам \<состояние входной сигнал\> (<tex>a_{m}</tex>, <tex>z_{f}</tex>) ставит в соответствие выходной сигнал АА <tex>w_{g}</tex>, т.е. <tex>w_{g}=λ(a_{m},z_{f})</tex>, <tex>w_{g}\in W</tex>.
+
* <tex>\lambda</tex> {{---}} функция выходов АА, которая некоторым парам состояние {{---}} входной сигнал <tex>(a_{m}</tex>, <tex>z_{f})</tex> ставит в соответствие выходной сигнал АА <tex>w_{g}</tex>, т.е. <tex>w_{g}=λ(a_{m},z_{f})</tex>, <tex>w_{g}\in W</tex>.
  
6. <tex>a_{1}</tex> - начальное состояние. АА работает в дискретные моменты времени, и в момент времени <tex>t=0</tex> автомат всегда находится в состоянии <tex>a_{1}</tex>.
+
* <tex>a_{1}</tex> {{---}} начальное состояние. АА работает в дискретные моменты времени, и в момент времени <tex>t=0</tex> автомат всегда находится в состоянии <tex>a_{1}</tex>.
 
}}
 
}}
 +
 +
[[File:aa_work.png|300px|thumb|right|Работа Абстрактного автомата]]
  
 
Выходные сигналы АА зависят от того, что поступало на его вход раньше.
 
Выходные сигналы АА зависят от того, что поступало на его вход раньше.
Строка 37: Строка 38:
 
|}
 
|}
  
В автоматах Мура выходной сигнал определяется только состоянием автомата в какой-то момент времени и не зависит от входного сигнала в этот же момент времени.
+
В автоматах Мура выходные воздействия записаны на состояниях, а в автомате Мили — на переходах.
 +
 
 +
== Применение автоматов Мура и Мили ==
 +
 
 +
Автоматы Мура и Мили широко применяются при проектировании цифровых устройств на основе программируемых логических интегральных схем (ПЛИС).
 +
 
 +
Основное преимущество использования автомата Мили заключается в возможности реакции автомата в течение текущего такта, что обусловлено зависимостью текущей выходной комбинации от текущей входной комбинации <tex>a_{i}</tex>.
 +
 
 +
Наличие минимальной выходной задержки, связанной с переключением выходного регистра, отсутствие нестабильности переходного процесса на выходе автомата, отсутствие сквозного распространения сигнала через комбинационную схему от входа до выхода автомата, простота описания на языках описания аппаратуры HDL делает автомат Мура практически незаменимым.
 +
 
 +
Также автоматы Мура и взаимодействующие автоматы Мили используются в генетическом программировании (например, для решения задачи об "Умном муравье"
 +
<ref>[http://is.ifmo.ru/works/2008/Vestnik/53/09-genetic-automata-smart-ant.pdf Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об "Умном муравье"]</ref>).
 +
 
 +
=== Автомат, регулирующий пешеходный переход===
 +
[[File:Пешеходный переход.png|right]]
 +
Рассмотрим автомат, регулирующий пешеходный переход по запросу пешеходов. Внешние события автомата — это события нажатия пешеходами кнопки-запроса на тротуаре и исчерпание тайм-аута. Автомат строится как автомат Мура, в котором выход — регулирование светофора и разрешающий сигнал на переход — это потенциальные сигналы, являющиеся функциями состояния.
 +
 
 +
Выход автомата в каждом состоянии определяется парой <tex>\langle</tex>Светофор транспорта; светофор пешехода<tex>\rangle</tex>. Например, в состоянии <tex>S_1</tex> управляющий автомат устанавливает <tex>\langle</tex>З; К<tex>\rangle</tex>, то есть включёнными зеленый свет транспорту и красный — пешеходам. В состоянии <tex>S_6</tex> установлен <tex>\langle</tex>Ж, К; К<tex>\rangle</tex>, то есть желтый и красный свет транспорту (приготовиться) и красный — пешеходам. В начальном состоянии <tex>S_0</tex> разрешен проезд транспорту, а пешеходам движение запрещено.
 +
 
 +
В состояниях <tex>S_4</tex>, <tex>S_5</tex> при запрещающем сигнале транспорту зеленый сигнал пешеходам мигает каждые <tex>t_0</tex> секунд в течение <tex>t_2</tex> секунд. Запрос на переход принимается только в состоянии <tex>S_0</tex>, в остальных состояниях он игнорируется. Задержки (тайм-ауты <tex>t_0</tex> — <tex>t_3</tex>) устанавливаются в момент перехода автомата в данное состояние, по исчерпании тайм-аута автомат переходит в следующее состояние. В гиперсостоянии <tex>Q</tex>, объединяющему пару состояний <tex>S_4</tex> и <tex>S_5</tex>, автомат находится ровно <tex>t_2</tex> секунд: внутренние переходы не срывают тайм-аута.
 +
 
 +
Именно для этого удобно использовать гиперсостояние <tex>Q</tex>.
 +
 
 +
===Торговый автомат===
 +
[[File:Автомат шоколадок.png|right]]
 +
В качестве примера применения автомата Мили рассмотрим автомат по продаже шоколадок стоимостью <tex>20</tex> рублей, принимающий монеты номиналом в <tex>5</tex> и <tex>10</tex> рублей и возвращающий сдачу, если это необходимо.
 +
 
 +
Состояний автомата всего четыре: <tex>0</tex>, <tex>5</tex>, <tex>10</tex> и <tex>15</tex> рублей.
 +
 
 +
Входных сигналов <tex>Z</tex> два: <tex>Z_5</tex> — <tex>5</tex> рублей и <tex>Z_{10}</tex> — <tex>10</tex> рублей.
 +
 
 +
Выходных сигналов <tex>W</tex> три: <tex>W_{n}</tex> — ничего не выдавать, <tex>W_{0}</tex> — выдать шоколадку и <tex>0</tex> рублей сдачи, <tex>W_{5}</tex> — выдать шоколадку и <tex>5</tex> рублей сдачи.
 +
 
 +
Например, если у человека есть одна монета номиналом в <tex>10</tex> рублей и две монеты номиналом в <tex>5</tex> рублей и монеты забрасываются в порядке <tex>10</tex>, <tex>5</tex> и <tex>5</tex> рублей, то происходит следующее:
 +
:# Автомат переходит в состояние <tex>10</tex>р. и ничего не выдает;
 +
:# Автомат переходит в состояние <tex>15</tex>р. и ничего не выдает;
 +
:# Автомат переходит в состояние <tex>0</tex>р., выдает шоколадку и не возвращает сдачу.
  
 
== Способы задания автоматов ==
 
== Способы задания автоматов ==
 
=== Табличный способ задания автомата Мили ===
 
=== Табличный способ задания автомата Мили ===
 +
 
Автомат Мили может быть задан таблицей переходов и таблицей выходов.
 
Автомат Мили может быть задан таблицей переходов и таблицей выходов.
  
Строка 47: Строка 85:
 
{| class="wikitable" style="margin-left: 20px"
 
{| class="wikitable" style="margin-left: 20px"
 
|-  
 
|-  
| style="background: white; padding: 5px 30px" |  || style="background: white; padding: 5px 30px" | <tex>a_{m}</tex> || style="background: white; padding: 5px 30px" |  
+
| style="background: white; padding: 5px 15px" |  || style="background: white; padding: 5px 15px" | <tex>a_{m}</tex> || style="background: white; padding: 5px 15px" |  
 
|-  
 
|-  
| style="background: white; padding: 5px 30px" | <tex>z_{f}</tex> || style="background: white; padding: 5px 30px" | <tex>a_{s}</tex> || style="background: white; padding: 5px 30px" | <tex>=\delta (a_{m}, z_{f})</tex>
+
| style="background: white; padding: 5px 15px" | <tex>z_{f}</tex> || style="background: white; padding: 5px 15px" | <tex>a_{s}</tex> || style="background: white; padding: 5px 15px" | <tex>=\delta (a_{m}, z_{f})</tex>
 
|}
 
|}
  
Строка 56: Строка 94:
 
{| class="wikitable" style="margin-left: 20px"
 
{| class="wikitable" style="margin-left: 20px"
 
|-  
 
|-  
| style="background: white; padding: 5px 30px" |  || style="background: white; padding: 5px 30px" | <tex>a_{m}</tex> || style="background: white; padding: 5px 30px" |  
+
| style="background: white; padding: 5px 15px" |  || style="background: white; padding: 5px 15px" | <tex>a_{m}</tex> || style="background: white; padding: 5px 15px" |  
 
|-  
 
|-  
| style="background: white; padding: 5px 30px" | <tex>z_{f}</tex> || style="background: white; padding: 5px 30px" | <tex>w_{g}</tex> || style="background: white; padding: 5px 30px" | <tex>=\lambda (a_{m}, z_{f})</tex>
+
| style="background: white; padding: 5px 15px" | <tex>z_{f}</tex> || style="background: white; padding: 5px 15px" | <tex>w_{g}</tex> || style="background: white; padding: 5px 15px" | <tex>=\lambda (a_{m}, z_{f})</tex>
 
|}
 
|}
  
Строка 65: Строка 103:
 
{| class="table"
 
{| class="table"
 
|- style="background: white; border: 0px solid white" |
 
|- style="background: white; border: 0px solid white" |
| style="padding: 10px 70px 10px 20px" |
+
| style="padding: 10px 70px 10px 15px" |
<div style="font-size: 16px; font-weight:bold">Таблица переходов</div>
+
<div style="font-size: 16px">Таблица переходов</div>
  
 
{| class="wikitable"
 
{| class="wikitable"
 
|-  
 
|-  
| style="background: white; padding: 5px 20px" | <tex>\delta</tex> || style="background: white; padding: 5px 20px" | <tex>a_{1}</tex> || style="background: white; padding: 5px 20px" | <tex>a_{2}</tex> || style="background: white; padding: 5px 20px" | <tex>a_{3}</tex>
+
| style="background: white; padding: 5px 15px" | <tex>\delta</tex> || style="background: white; padding: 5px 15px" | <tex>a_{1}</tex> || style="background: white; padding: 5px 15px" | <tex>a_{2}</tex> || style="background: white; padding: 5px 15px" | <tex>a_{3}</tex>
 
|-  
 
|-  
| style="background: white; padding: 5px 20px" | <tex>z_{1}</tex> || style="background: white; padding: 5px 20px" | <tex>a_{1}</tex> || style="background: white; padding: 5px 20px" | <tex>a_{3}</tex> || style="background: white; padding: 5px 20px" | <tex>a_{1}</tex>
+
| style="background: white; padding: 5px 15px" | <tex>z_{1}</tex> || style="background: white; padding: 5px 15px" | <tex>a_{1}</tex> || style="background: white; padding: 5px 15px" | <tex>a_{3}</tex> || style="background: white; padding: 5px 15px" | <tex>a_{1}</tex>
 
|-  
 
|-  
| style="background: white; padding: 5px 20px" | <tex>z_{2}</tex> || style="background: white; padding: 5px 20px" | <tex>a_{2}</tex> || style="background: white; padding: 5px 20px" | <tex>a_{1}</tex> || style="background: white; padding: 5px 20px" | <tex>a_{2}</tex>
+
| style="background: white; padding: 5px 15px" | <tex>z_{2}</tex> || style="background: white; padding: 5px 15px" | <tex>a_{2}</tex> || style="background: white; padding: 5px 15px" | <tex>a_{1}</tex> || style="background: white; padding: 5px 15px" | <tex>a_{2}</tex>
 
|}
 
|}
  
 
||
 
||
<div style="font-size: 16px; font-weight:bold">Таблица выходов</div>
+
<div style="font-size: 16px">Таблица выходов</div>
  
 
{| class="wikitable"
 
{| class="wikitable"
 
|-  
 
|-  
| style="background: white; padding: 5px 20px" | <tex>\lambda</tex> || style="background: white; padding: 5px 20px" | <tex>a_{1}</tex> || style="background: white; padding: 5px 20px" | <tex>a_{2}</tex> || style="background: white; padding: 5px 20px" | <tex>a_{3}</tex>
+
| style="background: white; padding: 5px 15px" | <tex>\lambda</tex> || style="background: white; padding: 5px 15px" | <tex>a_{1}</tex> || style="background: white; padding: 5px 15px" | <tex>a_{2}</tex> || style="background: white; padding: 5px 15px" | <tex>a_{3}</tex>
 
|-  
 
|-  
| style="background: white; padding: 5px 20px" | <tex>z_{1}</tex> || style="background: white; padding: 5px 20px" | <tex>w_{2}</tex> || style="background: white; padding: 5px 20px" | <tex>w_{2}</tex> || style="background: white; padding: 5px 20px" | <tex>w_{2}</tex>
+
| style="background: white; padding: 5px 15px" | <tex>z_{1}</tex> || style="background: white; padding: 5px 15px" | <tex>w_{2}</tex> || style="background: white; padding: 5px 15px" | <tex>w_{2}</tex> || style="background: white; padding: 5px 15px" | <tex>w_{2}</tex>
 
|-  
 
|-  
| style="background: white; padding: 5px 20px" | <tex>z_{2}</tex> || style="background: white; padding: 5px 20px" | <tex>w_{1}</tex> || style="background: white; padding: 5px 20px" | <tex>w_{1}</tex> || style="background: white; padding: 5px 20px" | <tex>w_{2}</tex>
+
| style="background: white; padding: 5px 15px" | <tex>z_{2}</tex> || style="background: white; padding: 5px 15px" | <tex>w_{1}</tex> || style="background: white; padding: 5px 15px" | <tex>w_{1}</tex> || style="background: white; padding: 5px 15px" | <tex>w_{2}</tex>
 
|}
 
|}
  
 
|}
 
|}
 +
 +
=== Графический способ задания автомата Мили ===
 +
 +
На рисунке приведен граф автомата Мили на 3 состояния, имеющий 2 входных сигнала и 2 выходных сигнала (см. предыдущий пример).
 +
 +
[[File:aa_mili_ex1.png|300px]]
  
 
=== Табличный способ задания автомата Мура ===
 
=== Табличный способ задания автомата Мура ===
В автомате Мура выходной сигнал зависит только от состояния автомата и не зависит от входного сигнала. Поэтому достаточно для задания автомата Мура в таблице переходов добавить одну строку.
+
 
 +
В автомате Мура выходной сигнал зависит только от состояния автомата и не зависит от входного сигнала.
 +
 
 +
Поэтому достаточно для задания автомата Мура в таблице переходов добавить одну строку.
  
 
{| class="wikitable" style="margin-left: 20px"
 
{| class="wikitable" style="margin-left: 20px"
Строка 104: Строка 151:
 
| style="background: white; padding: 5px 15px" | <tex>z_{2}</tex> || style="background: white; padding: 5px 15px" | <tex>a_{3}</tex> || style="background: white; padding: 5px 15px" | <tex>a_{3}</tex> || style="background: white; padding: 5px 15px" | <tex>a_{1}</tex> || style="background: white; padding: 5px 15px" | <tex>a_{1}</tex> || style="background: white; padding: 5px 15px" | <tex>a_{4}</tex>
 
| style="background: white; padding: 5px 15px" | <tex>z_{2}</tex> || style="background: white; padding: 5px 15px" | <tex>a_{3}</tex> || style="background: white; padding: 5px 15px" | <tex>a_{3}</tex> || style="background: white; padding: 5px 15px" | <tex>a_{1}</tex> || style="background: white; padding: 5px 15px" | <tex>a_{1}</tex> || style="background: white; padding: 5px 15px" | <tex>a_{4}</tex>
 
|}
 
|}
 +
 +
=== Графический способ задания автомата Мура ===
 +
 +
На рисунке приведен граф автомата Мура на 5 состояний, имеющий 2 входных сигнала и 2 выходных сигнала.
 +
 +
[[File:aa_moor_ex1.png|300px]]
 +
 +
== Реакция автоматов на входное слово ==
 +
=== Автомат Мили ===
 +
 +
Допустим, входное слово <tex>\xi</tex> поступает на вход автомата буква за буквой.
 +
 +
Выходное слово <tex>\omega</tex> называется реакцией автомата Мили на входное слово <tex>\xi</tex> в состоянии <tex>a_{1}</tex>строится по таблице переходов и выходов).
 +
 +
[[File:aa_mili_ex2.png|300px]]
 +
 +
Реакцию автомата на входное слово <tex>\xi</tex> можно заменить обходом графа.
 +
 +
=== Автомат Мура ===
 +
 +
Выходное слово <tex>\omega</tex> называется реакцией автомата Мура на входное слово <tex>\xi</tex> в состоянии <tex>a_{1}</tex>.
 +
 +
[[File:aa_moor_ex2.png|300px]]
 +
 +
В рассматриваемом примере для автоматов Мили и Мура реакции автоматов на одинаковое входное слово совпадают, но они сдвинуты на один такт. Автоматы Мили и Мура дающие одинаковые реакции на одинаковые входные слова называются эквивалентными. Данное замечание приводит к задаче построения эквивалентных автоматов, дающих одинаковые реакции на одинаковые входные слова.
 +
 +
== Эквивалентность автоматов Мили и Мура ==
 +
 +
Автомат Мура переходит в автомат Мили, если всем переходам в состояние поставить выходные воздействия этого состояния. После таких преобразований получим эквивалентный автомат Мили.
 +
 +
Однако, чтобы преобразовать автомат Мили в автомат Мура такой алгоритм не подходит, т.к. в одно состояние могут вести разные переходы. Но можно просто добавить новых состояний, устанавливая необходимые соответствия.
 +
 +
Далее будет приведено формальное доказательство факта эквивалентности с явным предъявлением конструкции.
 +
 +
{{Теорема
 +
|about=Эквивалентность автоматов Мура и Мили
 +
|statement=
 +
Для каждого автомата Мили может быть построен эквивалентный ему автомат Мура, и обратно {{---}} для каждого автомата Мура может быть построен эквивалентный ему автомат Мили.
 +
|proof=
 +
Для доказательства опишем алгоритмы взаимной трансформации моделей Мили и Мура и покажем эквивалентность получающихся автоматов. При этом в автоматах Мура будем пренебрегать выходным сигналом <tex>\lambda(a_{1})</tex>, связанным с начальным состоянием.
 +
}}
 +
 +
=== Переход от автомата Мура к автомату Мили ===
 +
Шестикомпонентным набором с индексом А будем обозначать автомат Мура, а с индексом В {{---}} автомат Мили.
 +
 +
Пусть задан автомат Мура.
 +
 +
[[File:aa_moor_ex3.png|300px]]
 +
 +
Требуется перейти к автомату Мили
 +
 +
<tex>S_{B} = (A_{B}, Z_{B}, W_{B}, \delta _{B}, \lambda _{B}, a_{1B}</tex>),
 +
 +
у которого <tex>Z_{A} = Z_{B}</tex>, <tex>W_{A} = W_{B}</tex>, т.е. входные и выходные алфавиты совпадают.
 +
 +
Рассмотрим пример, в котором <tex>Z_{А} = \{z_{1}, z_{2}\} = Z_{B}</tex>, <tex>W_{A} = \{w_{1}, w_{2}\} = W_{B}</tex>, <tex>a_{1A} = a_{1B}</tex>, алфавит состояний автомата Мура содержит четыре элемента.
 +
 +
При переходе от автомата Мура к автомату Мили алфавиты состояний также совпадают, т.е. <tex>A_{A} = A_{B}</tex>.
 +
 +
Для определения соответствия между функциями переходов выходов автоматов Мура и Мили воспользуемся следующей вспомогательной таблицей.
 +
 +
{| class="table" style="margin-left: 20px; text-align: center; border: 0px"
 +
|-
 +
| style="background: white; padding: 5px 35px" | Мура
 +
| style="background: white; padding: 5px 35px" | Мили
 +
|-
 +
| style="background: white; padding: 5px 35px" | <tex>\delta _{A} (a_{m}, z_{f}) = a_{s}</tex>
 +
| style="background: white; padding: 5px 35px" | <tex>\delta _{B} (a_{m}, z_{f}) = a_{s}</tex>
 +
|-
 +
| style="background: white; padding: 5px 35px" | <tex>\lambda _{A}(a_{m}) = w_{g}</tex>
 +
| style="background: white; padding: 5px 35px" | <tex>\lambda _{B} (a_{m}, z_{f}) = w_{g}</tex>
 +
|-
 +
| style="background: white; padding: 5px 35px" | [[File:moor_transition.png|200px]]
 +
| style="background: white; padding: 5px 35px" | [[File:mili_transition.png|200px]]
 +
|}
 +
 +
При переходе от автомата Мура к автомату Мили функции переходов также совпадают, а для определения функции выходов выходные сигналы с вершин опускается на входные дуги.
 +
 +
Проделав такие преобразования мы должны доказать, что получили автомат Мили, эквивалентный автомату Мура, т.е. что реакции автоматов на одинаковые входные воздействия совпадают.
 +
 +
При таком переходе (Мура к Мили) число состояний совпадает.
 +
 +
{{Утверждение
 +
|statement=
 +
Полученный автомат эквивалентен исходному
 +
|proof=
 +
Пусть символ <tex>z_{f}</tex> поступает на вход автомата Мура <tex>S_{A}</tex>, который находится в состоянии <tex>a_{m}</tex>. Следовательно, <tex>S_{A}</tex> перейдет в состояние <tex>a_{s} = \delta _{A}(a_{m}, z_{f})</tex> и выдаст сигнал <tex>w_{g} = \lambda _{A}(a_{s})</tex>.
 +
 +
Соответствующий автомат Мили <tex>S_{B}</tex> из состояния <tex>a_{m}</tex> также перейдет в состояние <tex>a_{s} = \delta _{B}(a_{m}, z_{f}) = \delta _{A}(a_{m}, z_{f})</tex> и выдаст тот же сигнал <tex>w_{g} = \lambda _{B}(a_{m}, z_{f}) = \lambda _{A}(\delta _{A}(a_{m}, z_{f})) = \lambda _{A}(a_{s}) = w_{g}</tex>.
 +
 +
Таким образом, для выходной последовательности длины 1 поведение автоматов <tex>S_{1}</tex> и <tex>S_{2}</tex> полностью совпадает. Далее по индукции получаем эквивалентность автоматов.
 +
}}
 +
 +
=== Переход от автомата Мили к автомату Мура ===
 +
 +
Пусть задан автомат Мили <tex>S_{B} = (A_{B}, Z_{B}, W_{B}, \delta _{B}, \lambda _{B}, a_{1B})</tex>.
 +
 +
[[File:aa_mili_ex3.png|300px]]
 +
 +
Требуется перейти к автомату Мура
 +
 +
<tex>S_{A} = (A_{A}, Z_{A}, W_{A}, \delta _{A}, \lambda _{A}, a_{1A})</tex>,
 +
 +
у которого <tex>Z_{B} = Z_{A}</tex>; <tex>W_{B} = W_{A}</tex>, т.е. входные и выходные алфавиты совпадают.
 +
 +
Рассмотрим пример, в котором <tex>Z_{B} = \{z_{1}, z_{2}\} = Z_{А}</tex>, <tex>W_{B} = \{w_{1}, w_{2}\} = W_{A}</tex>, алфавит состояний автомата Мили содержит три элемента.
 +
 +
Для определения алфавита состояний, функций переходов и выходов автомата Мура воспользуемся следующей вспомогательной таблицей.
 +
 +
{| class="table" style="margin-left: 20px; text-align: center; border: 0px"
 +
|-
 +
| style="background: white; padding: 5px 35px" | Мура
 +
| style="background: white; padding: 5px 35px" | Мили
 +
|-
 +
| style="background: white; padding: 5px 35px" | [[File:moor_transition2.png|150px]]
 +
| style="background: white; padding: 5px 35px" | [[File:mili_transition2.png|230px]]
 +
|}
 +
 +
В данном случае <tex>A_{B} \neq A_{A}</tex>.
 +
 +
При таком переходе (Мили к Мура) каждому состоянию автомата Мили <tex>a_{s}</tex> ставится в соответствие множество всевозможных пар <tex>a_{s} \rightarrow A_{s} = \{( a_{s}, w_{g}) | a_{s} = \delta(a_{m}, z_{f}), w_{g} = \lambda(a_{m}, z_{f})\}</tex>, где <tex>a_{s}</tex> есть функция <tex>\delta</tex> от состояния и входного сигнала, <tex>w_{g}</tex> функция <tex>\lambda</tex> от состояния и входного сигнала.
 +
 +
'''Пример''':
 +
 +
{| class="table" style="margin-left: 20px; text-align: center; border: 0px"
 +
|-
 +
| style="background: white; padding: 5px 35px" | Мура
 +
| style="background: white; padding: 5px 35px" | Мили
 +
|-
 +
| style="background: white; padding: 5px 35px" | [[File:ex_1.png|120px]]
 +
| style="background: white; padding: 5px 35px" | <tex>A_{s} = \{(a_{s}, w_{1}), (a_{s}, w_{2}), (a_{s}, w_{3})\}</tex>
 +
|}
 +
 +
Для состояния:
 +
 +
{| class="table" style="margin-left: 20px; border: 0px solid white"
 +
|-
 +
| style="background: white; padding: 5px 60px 5px 0" | <tex>a_{1}: A_{1} = \left \{ \begin {array} {crl} (a_{1}, w_{1}) = b_{1} \\ (a_{1}, w_{2}) = b_{2} \\ \end {array} \right.</tex>
 +
| style="background: white; padding: 5px 60px 5px 0" | <tex>a_{2}: A_{2} = \left \{ \begin {array} {crl} (a_{2}, w_{1}) = b_{3} \\ (a_{2}, w_{2}) = b_{4} \\ \end {array} \right.</tex>
 +
| style="background: white; padding: 5px 0" | <tex>a_{3}: A_{3} = \{ (a_{3}, w_{1}) \} = b_{5}</tex>
 +
|}
 +
 +
В качестве начального состояния результирующего автомата может быть выбрано любое состояние Мура, порожденное начальным состоянием автомата Мили, т.е. состояния <tex>b_{1}</tex> или <tex>b_{2}</tex>.
 +
 +
При определении функции переходов результирующего автомата Мура из всех состояний, порожденных одним состоянием автомата Мили, должны быть переходы под воздействием одинаковых входных сигналов.
 +
 +
Поскольку в автомате Мура выходной сигнал зависит только от состояния автомата, то в примере рядом с состояниями проставим соответствующие выходные сигналы.
 +
 +
[[File:ex_2.png|300px]]
 +
 +
И так если осуществить следующие преобразования, то получим:
 +
 +
{| class="table" style="margin-left: 20px; border: 0px solid white"
 +
|-
 +
| style="background: white; padding: 5px 70px 5px 0" | Мили
 +
| style="background: white; padding: 5px 70px 5px 0" | Мура
 +
| style="background: white; padding: 5px 0" | Мили
 +
|-
 +
| style="background: white; padding: 0px 70px 0px 0" | <tex>S_{1} \rightarrow</tex>
 +
| style="background: white; padding: 0px 70px 0px 0" | <tex>S_{2} \rightarrow</tex>
 +
| style="background: white; padding: 0" | <tex>S_{3}</tex>
 +
|-
 +
| style="background: white; padding: 5px 70px 5px 0" | 3 состояния
 +
| style="background: white; padding: 5px 70px 5px 0" | 5 состояний
 +
| style="background: white; padding: 5px 0" | 5 состояний
 +
|}
 +
 +
Можно утверждать, что если <tex>S_{1}</tex> эквивалентно <tex>S_{2}</tex>, а <tex>S_{2}</tex> эквивалентно <tex>S_{3}</tex>, то <tex>S_{1}</tex> эквивалентно <tex>S_{3}</tex> (т.е. эквивалентность обладает свойством транзитивности).
 +
 +
{{Утверждение
 +
|statement=
 +
Полученный автомат эквивалентен исходному
 +
|proof=
 +
Доказательство эквивалентности автоматов <tex>S_{A}</tex> и <tex>S_{B}</tex> аналогично предыдущему случаю.
 +
}}
 +
 +
Методы взаимной транспозиции автоматов Мили и Мура показывают, что при переходе от автомата Мили к автомату Мура число состояний принципиально не меняется. В то время как при обратном переходе в автомат Мура число состояний, как правило, увеличивается. Вследствие транзитивности отношения эквивалентности два автомата Мили, первый из которых получен из автомата Мура, так же будут эквивалентны, но у второго автомата число состояний будет больше. Таким образом эквивалентные между собой автоматы могут иметь различное число состояний. В связи с чем и возникает задача нахождения минимального автомата в классе эквивалентных между собой автоматов. Существование для любого абстрактного автомата эквивалентного ему абстрактного автомата с минимальным числом внутренних состояний впервые было доказано Муром.
 +
 +
== См. также ==
 +
* [[Локальные автоматы]]
 +
* [[Двусторонний детерминированный конечный автомат]]
 +
* [[Квантовый конечный автомат]]
 +
 +
==Примечания==
 +
<references/>
 +
 +
==Источники информации==
 +
<references/>
 +
* ''Ожиганов А.А.'' Теория автоматов: Учебное пособие. СПб.: НИУ ИТМО, 2013 — С. 84.
 +
* ''Богаченко Н.Ф., Файзуллин Р.Т.'' Синтез дискретных автоматов: Учебное пособие. Омск: Издательство Наследие. Диалог-Сибирь, 2006.
 +
*[https://ru.wikipedia.org/wiki/Автомат_Мура Википедия {{---}} Автомат Мура]
 +
*[http://ofap.ulstu.ru/vt/Theory_of_automats/part1.htm Ofap.ulstu.ru {{---}} Абстрактные автоматы]
 +
*[http://www.kit-e.ru/assets/files/pdf/2011_12_27.pdf Николай Борисенко {{---}} Технические аспекты построения управляющих автоматов при проектировании цифровых устройств на основе современных ПЛИС]
 +
 +
[[Категория: Теория формальных языков]]
 +
 +
[[Категория: Автоматы и регулярные языки]]
 +
 +
[[Категория: Другие автоматы]]

Текущая версия на 19:15, 4 сентября 2022

Определение:
Абстрактный автомат (англ. Abstract Machine) является математической моделью дискретного устройства и описывается шестикомпонентным набором [math]S=(A, Z, W, \delta, \lambda, a_{1})[/math], где
  • [math]A=\{a_{1}, \dots, a_{m}, \dots, a_{M}\}[/math] — множество состояний.
  • [math]Z=\{z_{1}, \dots, z_{f}, \dots, z_{F}\}[/math] — множество входных сигналов.
  • [math]W=\{w_{1}, \dots, w_{g}, \dots, w_{G}\}[/math] — множество выходных сигналов.
  • [math]\delta[/math] — функция переходов АА, которая некоторым парам состояние — входной сигнал [math](a_{m}[/math], [math]z_{f})[/math] ставит в соответствие состояние АА [math]a_{s}[/math], т.е. [math]a_{s} = δ(a_{m}, z_{f})[/math], [math]a_{s}\in A[/math].
  • [math]\lambda[/math] — функция выходов АА, которая некоторым парам состояние — входной сигнал [math](a_{m}[/math], [math]z_{f})[/math] ставит в соответствие выходной сигнал АА [math]w_{g}[/math], т.е. [math]w_{g}=λ(a_{m},z_{f})[/math], [math]w_{g}\in W[/math].
  • [math]a_{1}[/math] — начальное состояние. АА работает в дискретные моменты времени, и в момент времени [math]t=0[/math] автомат всегда находится в состоянии [math]a_{1}[/math].


Работа Абстрактного автомата

Выходные сигналы АА зависят от того, что поступало на его вход раньше.

В каждый момент времени АА, будучи в состоянии [math]a_{m}^{t}[/math], способен воспринимать одну из букв входного алфавита [math]z_{f}^{t}[/math]. В соответствии с функцией [math]\delta[/math], АА перейдет в состояние [math]a_{1}^{t+1}[/math] с выдачей выходного сигнала, который вырабатывается в соответствии с функцией выходов [math]\lambda[/math].

Рассмотрим функционирование автоматов Мура и Мили.

Автомат Мили

[math]a(t+1) = \delta (a(t), z(t))[/math]

[math]w(t) = \lambda (a(t), z(t))[/math]

Автомат Мура

[math]a(t+1) = \delta (a(t), z(t))[/math]

[math]w(t) = \lambda (a(t))[/math]

В автоматах Мура выходные воздействия записаны на состояниях, а в автомате Мили — на переходах.

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

Автоматы Мура и Мили широко применяются при проектировании цифровых устройств на основе программируемых логических интегральных схем (ПЛИС).

Основное преимущество использования автомата Мили заключается в возможности реакции автомата в течение текущего такта, что обусловлено зависимостью текущей выходной комбинации от текущей входной комбинации [math]a_{i}[/math].

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

Также автоматы Мура и взаимодействующие автоматы Мили используются в генетическом программировании (например, для решения задачи об "Умном муравье" [1]).

Автомат, регулирующий пешеходный переход

Пешеходный переход.png

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

Выход автомата в каждом состоянии определяется парой [math]\langle[/math]Светофор транспорта; светофор пешехода[math]\rangle[/math]. Например, в состоянии [math]S_1[/math] управляющий автомат устанавливает [math]\langle[/math]З; К[math]\rangle[/math], то есть включёнными зеленый свет транспорту и красный — пешеходам. В состоянии [math]S_6[/math] установлен [math]\langle[/math]Ж, К; К[math]\rangle[/math], то есть желтый и красный свет транспорту (приготовиться) и красный — пешеходам. В начальном состоянии [math]S_0[/math] разрешен проезд транспорту, а пешеходам движение запрещено.

В состояниях [math]S_4[/math], [math]S_5[/math] при запрещающем сигнале транспорту зеленый сигнал пешеходам мигает каждые [math]t_0[/math] секунд в течение [math]t_2[/math] секунд. Запрос на переход принимается только в состоянии [math]S_0[/math], в остальных состояниях он игнорируется. Задержки (тайм-ауты [math]t_0[/math][math]t_3[/math]) устанавливаются в момент перехода автомата в данное состояние, по исчерпании тайм-аута автомат переходит в следующее состояние. В гиперсостоянии [math]Q[/math], объединяющему пару состояний [math]S_4[/math] и [math]S_5[/math], автомат находится ровно [math]t_2[/math] секунд: внутренние переходы не срывают тайм-аута.

Именно для этого удобно использовать гиперсостояние [math]Q[/math].

Торговый автомат

Автомат шоколадок.png

В качестве примера применения автомата Мили рассмотрим автомат по продаже шоколадок стоимостью [math]20[/math] рублей, принимающий монеты номиналом в [math]5[/math] и [math]10[/math] рублей и возвращающий сдачу, если это необходимо.

Состояний автомата всего четыре: [math]0[/math], [math]5[/math], [math]10[/math] и [math]15[/math] рублей.

Входных сигналов [math]Z[/math] два: [math]Z_5[/math][math]5[/math] рублей и [math]Z_{10}[/math][math]10[/math] рублей.

Выходных сигналов [math]W[/math] три: [math]W_{n}[/math] — ничего не выдавать, [math]W_{0}[/math] — выдать шоколадку и [math]0[/math] рублей сдачи, [math]W_{5}[/math] — выдать шоколадку и [math]5[/math] рублей сдачи.

Например, если у человека есть одна монета номиналом в [math]10[/math] рублей и две монеты номиналом в [math]5[/math] рублей и монеты забрасываются в порядке [math]10[/math], [math]5[/math] и [math]5[/math] рублей, то происходит следующее:

  1. Автомат переходит в состояние [math]10[/math]р. и ничего не выдает;
  2. Автомат переходит в состояние [math]15[/math]р. и ничего не выдает;
  3. Автомат переходит в состояние [math]0[/math]р., выдает шоколадку и не возвращает сдачу.

Способы задания автоматов

Табличный способ задания автомата Мили

Автомат Мили может быть задан таблицей переходов и таблицей выходов.

В таблице переходов АА Мили на пересечении столбца [math]a_{m}[/math] и строки [math]z_{f}[/math] записывается состояние [math]a_{s}[/math], которое есть функция [math]\delta[/math] от [math]a_{m}[/math] и [math]z_{f}[/math]

[math]a_{m}[/math]
[math]z_{f}[/math] [math]a_{s}[/math] [math]=\delta (a_{m}, z_{f})[/math]

В таблице выходов на пересечении столбца [math]a_{m}[/math] и строки [math]z_{f}[/math] записывается выходной сигнал, который есть функция [math]\lambda[/math] от [math]a_{m}[/math] и [math]z_{f}[/math].

[math]a_{m}[/math]
[math]z_{f}[/math] [math]w_{g}[/math] [math]=\lambda (a_{m}, z_{f})[/math]

Пример: Задание автомата Мили табличным способом (автомат имеет два входных сигнала, два выходных сигнала и три состояния).

Таблица переходов
[math]\delta[/math] [math]a_{1}[/math] [math]a_{2}[/math] [math]a_{3}[/math]
[math]z_{1}[/math] [math]a_{1}[/math] [math]a_{3}[/math] [math]a_{1}[/math]
[math]z_{2}[/math] [math]a_{2}[/math] [math]a_{1}[/math] [math]a_{2}[/math]
Таблица выходов
[math]\lambda[/math] [math]a_{1}[/math] [math]a_{2}[/math] [math]a_{3}[/math]
[math]z_{1}[/math] [math]w_{2}[/math] [math]w_{2}[/math] [math]w_{2}[/math]
[math]z_{2}[/math] [math]w_{1}[/math] [math]w_{1}[/math] [math]w_{2}[/math]

Графический способ задания автомата Мили

На рисунке приведен граф автомата Мили на 3 состояния, имеющий 2 входных сигнала и 2 выходных сигнала (см. предыдущий пример).

Aa mili ex1.png

Табличный способ задания автомата Мура

В автомате Мура выходной сигнал зависит только от состояния автомата и не зависит от входного сигнала.

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

[math]\lambda[/math] [math]w_{1}[/math] [math]w_{2}[/math] [math]w_{1}[/math] [math]w_{2}[/math] [math]w_{2}[/math]
[math]\delta[/math] [math]a_{1}[/math] [math]a_{2}[/math] [math]a_{3}[/math] [math]a_{4}[/math] [math]a_{5}[/math]
[math]z_{1}[/math] [math]a_{2}[/math] [math]a_{2}[/math] [math]a_{5}[/math] [math]a_{5}[/math] [math]a_{2}[/math]
[math]z_{2}[/math] [math]a_{3}[/math] [math]a_{3}[/math] [math]a_{1}[/math] [math]a_{1}[/math] [math]a_{4}[/math]

Графический способ задания автомата Мура

На рисунке приведен граф автомата Мура на 5 состояний, имеющий 2 входных сигнала и 2 выходных сигнала.

Aa moor ex1.png

Реакция автоматов на входное слово

Автомат Мили

Допустим, входное слово [math]\xi[/math] поступает на вход автомата буква за буквой.

Выходное слово [math]\omega[/math] называется реакцией автомата Мили на входное слово [math]\xi[/math] в состоянии [math]a_{1}[/math]строится по таблице переходов и выходов).

Aa mili ex2.png

Реакцию автомата на входное слово [math]\xi[/math] можно заменить обходом графа.

Автомат Мура

Выходное слово [math]\omega[/math] называется реакцией автомата Мура на входное слово [math]\xi[/math] в состоянии [math]a_{1}[/math].

Aa moor ex2.png

В рассматриваемом примере для автоматов Мили и Мура реакции автоматов на одинаковое входное слово совпадают, но они сдвинуты на один такт. Автоматы Мили и Мура дающие одинаковые реакции на одинаковые входные слова называются эквивалентными. Данное замечание приводит к задаче построения эквивалентных автоматов, дающих одинаковые реакции на одинаковые входные слова.

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

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

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

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

Теорема (Эквивалентность автоматов Мура и Мили):
Для каждого автомата Мили может быть построен эквивалентный ему автомат Мура, и обратно — для каждого автомата Мура может быть построен эквивалентный ему автомат Мили.
Доказательство:
[math]\triangleright[/math]
Для доказательства опишем алгоритмы взаимной трансформации моделей Мили и Мура и покажем эквивалентность получающихся автоматов. При этом в автоматах Мура будем пренебрегать выходным сигналом [math]\lambda(a_{1})[/math], связанным с начальным состоянием.
[math]\triangleleft[/math]

Переход от автомата Мура к автомату Мили

Шестикомпонентным набором с индексом А будем обозначать автомат Мура, а с индексом В — автомат Мили.

Пусть задан автомат Мура.

Aa moor ex3.png

Требуется перейти к автомату Мили

[math]S_{B} = (A_{B}, Z_{B}, W_{B}, \delta _{B}, \lambda _{B}, a_{1B}[/math]),

у которого [math]Z_{A} = Z_{B}[/math], [math]W_{A} = W_{B}[/math], т.е. входные и выходные алфавиты совпадают.

Рассмотрим пример, в котором [math]Z_{А} = \{z_{1}, z_{2}\} = Z_{B}[/math], [math]W_{A} = \{w_{1}, w_{2}\} = W_{B}[/math], [math]a_{1A} = a_{1B}[/math], алфавит состояний автомата Мура содержит четыре элемента.

При переходе от автомата Мура к автомату Мили алфавиты состояний также совпадают, т.е. [math]A_{A} = A_{B}[/math].

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

Мура Мили
[math]\delta _{A} (a_{m}, z_{f}) = a_{s}[/math] [math]\delta _{B} (a_{m}, z_{f}) = a_{s}[/math]
[math]\lambda _{A}(a_{m}) = w_{g}[/math] [math]\lambda _{B} (a_{m}, z_{f}) = w_{g}[/math]
Moor transition.png Mili transition.png

При переходе от автомата Мура к автомату Мили функции переходов также совпадают, а для определения функции выходов выходные сигналы с вершин опускается на входные дуги.

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

При таком переходе (Мура к Мили) число состояний совпадает.

Утверждение:
Полученный автомат эквивалентен исходному
[math]\triangleright[/math]

Пусть символ [math]z_{f}[/math] поступает на вход автомата Мура [math]S_{A}[/math], который находится в состоянии [math]a_{m}[/math]. Следовательно, [math]S_{A}[/math] перейдет в состояние [math]a_{s} = \delta _{A}(a_{m}, z_{f})[/math] и выдаст сигнал [math]w_{g} = \lambda _{A}(a_{s})[/math].

Соответствующий автомат Мили [math]S_{B}[/math] из состояния [math]a_{m}[/math] также перейдет в состояние [math]a_{s} = \delta _{B}(a_{m}, z_{f}) = \delta _{A}(a_{m}, z_{f})[/math] и выдаст тот же сигнал [math]w_{g} = \lambda _{B}(a_{m}, z_{f}) = \lambda _{A}(\delta _{A}(a_{m}, z_{f})) = \lambda _{A}(a_{s}) = w_{g}[/math].

Таким образом, для выходной последовательности длины 1 поведение автоматов [math]S_{1}[/math] и [math]S_{2}[/math] полностью совпадает. Далее по индукции получаем эквивалентность автоматов.
[math]\triangleleft[/math]

Переход от автомата Мили к автомату Мура

Пусть задан автомат Мили [math]S_{B} = (A_{B}, Z_{B}, W_{B}, \delta _{B}, \lambda _{B}, a_{1B})[/math].

Aa mili ex3.png

Требуется перейти к автомату Мура

[math]S_{A} = (A_{A}, Z_{A}, W_{A}, \delta _{A}, \lambda _{A}, a_{1A})[/math],

у которого [math]Z_{B} = Z_{A}[/math]; [math]W_{B} = W_{A}[/math], т.е. входные и выходные алфавиты совпадают.

Рассмотрим пример, в котором [math]Z_{B} = \{z_{1}, z_{2}\} = Z_{А}[/math], [math]W_{B} = \{w_{1}, w_{2}\} = W_{A}[/math], алфавит состояний автомата Мили содержит три элемента.

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

Мура Мили
Moor transition2.png Mili transition2.png

В данном случае [math]A_{B} \neq A_{A}[/math].

При таком переходе (Мили к Мура) каждому состоянию автомата Мили [math]a_{s}[/math] ставится в соответствие множество всевозможных пар [math]a_{s} \rightarrow A_{s} = \{( a_{s}, w_{g}) | a_{s} = \delta(a_{m}, z_{f}), w_{g} = \lambda(a_{m}, z_{f})\}[/math], где [math]a_{s}[/math] есть функция [math]\delta[/math] от состояния и входного сигнала, [math]w_{g}[/math] функция [math]\lambda[/math] от состояния и входного сигнала.

Пример:

Мура Мили
Ex 1.png [math]A_{s} = \{(a_{s}, w_{1}), (a_{s}, w_{2}), (a_{s}, w_{3})\}[/math]

Для состояния:

[math]a_{1}: A_{1} = \left \{ \begin {array} {crl} (a_{1}, w_{1}) = b_{1} \\ (a_{1}, w_{2}) = b_{2} \\ \end {array} \right.[/math] [math]a_{2}: A_{2} = \left \{ \begin {array} {crl} (a_{2}, w_{1}) = b_{3} \\ (a_{2}, w_{2}) = b_{4} \\ \end {array} \right.[/math] [math]a_{3}: A_{3} = \{ (a_{3}, w_{1}) \} = b_{5}[/math]

В качестве начального состояния результирующего автомата может быть выбрано любое состояние Мура, порожденное начальным состоянием автомата Мили, т.е. состояния [math]b_{1}[/math] или [math]b_{2}[/math].

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

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

Ex 2.png

И так если осуществить следующие преобразования, то получим:

Мили Мура Мили
[math]S_{1} \rightarrow[/math] [math]S_{2} \rightarrow[/math] [math]S_{3}[/math]
3 состояния 5 состояний 5 состояний

Можно утверждать, что если [math]S_{1}[/math] эквивалентно [math]S_{2}[/math], а [math]S_{2}[/math] эквивалентно [math]S_{3}[/math], то [math]S_{1}[/math] эквивалентно [math]S_{3}[/math] (т.е. эквивалентность обладает свойством транзитивности).

Утверждение:
Полученный автомат эквивалентен исходному
[math]\triangleright[/math]
Доказательство эквивалентности автоматов [math]S_{A}[/math] и [math]S_{B}[/math] аналогично предыдущему случаю.
[math]\triangleleft[/math]

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

См. также

Примечания

Источники информации