1632
правки
Изменения
м
1. * <tex>A=\{a_{1}, ...\dots, a_{m}, ...\dots, a_{M}\}</tex> {{- --}} множество состояний.
2. * <tex>Z=\{z_{1}, ...\dots, z_{f}, ...\dots, z_{F}\}</tex> {{--- }} множество входных сигналов.
3. * <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>.
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>.
6. * <tex>a_{1}</tex> {{--- }} начальное состояние. АА работает в дискретные моменты времени, и в момент времени <tex>t=0</tex> автомат всегда находится в состоянии <tex>a_{1}</tex>.
Выход автомата в каждом состоянии определяется парой <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>р., выдает шоколадку и не возвращает сдачу.
Требуется перейти к автомату Мили <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>, т.е. входные и выходные алфавиты совпадают.
Доказательство проводится по индукцииПри таком переходе (Мура к Мили) число состояний совпадает. {{Утверждение|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}, увеличивая слова на 1 получим доказательствоz_{f})) = \lambda _{A}(a_{s}) = w_{g}</tex>.
При таком переходе (Мура к Мили) число состояний Таким образом, для выходной последовательности длины 1 поведение автоматов <tex>S_{1}</tex> и <tex>S_{2}</tex> полностью совпадает.Далее по индукции получаем эквивалентность автоматов.}}
rollbackEdits.php mass rollback
{{Определение
|definition=
'''Абстрактный автомат''' (ААангл. ''Abstract Machine'') является математической моделью дискретного устройства и описывается шестикомпонентным набором <tex>S=(A, Z, W, \delta, \lambda, a_{1})</tex>, где
}}
[[File:aa_work.png|300px|thumb|right|Работа Абстрактного автомата]]
Выходные сигналы АА зависят от того, что поступало на его вход раньше.
|}
В автоматах Мура выходные воздействия записаны на состояниях, а в автомате Мили — на переходах. == Применение автоматов Мура и Мили == Автоматы Мура и Мили широко применяются при проектировании цифровых устройств на основе программируемых логических интегральных схем (ПЛИС). Основное преимущество использования автомата Мили заключается в возможности реакции автомата в течение текущего такта, что обусловлено зависимостью текущей выходной сигнал определяется только состоянием комбинации от текущей входной комбинации <tex>a_{i}</tex>. Наличие минимальной выходной задержки, связанной с переключением выходного регистра, отсутствие нестабильности переходного процесса на выходе автомата, отсутствие сквозного распространения сигнала через комбинационную схему от входа до выхода автомата , простота описания на языках описания аппаратуры HDL делает автомат Мура практически незаменимым. Также автоматы Мура и взаимодействующие автоматы Мили используются в какойгенетическом программировании (например, для решения задачи об "Умном муравье"<ref>[http://is.ifmo.ru/works/2008/Vestnik/53/09-genetic-automata-то момент времени smart-ant.pdf Применение генетических алгоритмов для генерации автоматов Мура и не зависит от входного сигнала систем взаимодействующих автоматов Мили в задаче об "Умном муравье"]</ref>). === Автомат, регулирующий пешеходный переход===[[File:Пешеходный переход.png|right]]Рассмотрим автомат, регулирующий пешеходный переход по запросу пешеходов. Внешние события автомата — это события нажатия пешеходами кнопки-запроса на тротуаре и исчерпание тайм-аута. Автомат строится как автомат Мура, в этот же момент временикотором выход — регулирование светофора и разрешающий сигнал на переход — это потенциальные сигналы, являющиеся функциями состояния.
== Способы задания автоматов ==
=== Табличный способ задания автомата Мили ===
Автомат Мили может быть задан таблицей переходов и таблицей выходов.
На рисунке приведен граф автомата Мили на 3 состояния, имеющий 2 входных сигнала и 2 выходных сигнала (см. предыдущий пример).
[[File:aa_mili_ex1.png|300px]]
=== Табличный способ задания автомата Мура ===
В автомате Мура выходной сигнал зависит только от состояния автомата и не зависит от входного сигнала. Поэтому достаточно для задания автомата Мура в таблице переходов добавить одну строку.
{| class="wikitable" style="margin-left: 20px"
На рисунке приведен граф автомата Мура на 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_{А} = \{z_{1}, z_{2}\} = Z_{B}</tex>, <tex>W_{A} = \{w_{1}, w_{2}\} = W_{B}</tex>, <tex>a_{1A} = a_{1B}</tex>, алфавит состояний автомата Мура содержит четыре элемента.
Для определения соответствия между функциями переходов выходов автоматов Мура и Мили воспользуемся следующей вспомогательной таблицей.
{| class="wikitabletable" style="margin-left: 20px; text-align: center; border: 0px"
|-
| style="background: white; padding: 5px 35px" | Мура
| 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]]
|}
Проделав такие преобразования мы должны доказать, что получили автомат Мили, эквивалентный автомату Мура, т.е. что реакции автоматов на одинаковые входные воздействия совпадают.
=== Переход от автомата Мили к автомату Мура ===
Пусть задан автомат Мили <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>.
'''Пример''':
{| 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>.|}
Для состояния:
|-
| 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_{12} = \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>
|}
Поскольку в автомате Мура выходной сигнал зависит только от состояния автомата, то в примере рядом с состояниями проставим соответствующие выходные сигналы.
[[File:ex_2.png|300px]]
И так если осуществить следующие преобразования, то получим:
Можно утверждать, что если <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 Николай Борисенко {{---}} Технические аспекты построения управляющих автоматов при проектировании цифровых устройств на основе современных ПЛИС] [[Категория: Теория формальных языков]] [[Категория: Автоматы и регулярные языки]] [[Категория: Другие автоматы]]
