Изменения
Нет описания правки
'''Абстрактный автомат''' (англ. ''Abstract Machine'') является математической моделью дискретного устройства и описывается шестикомпонентным набором <tex>S=(A, Z, W, \delta, \lambda, a_{1})</tex>, где
* <tex>A=\{a_{1}, ...\dots, a_{m}, ...\dots, a_{M}\}</tex> – {{---}} множество состояний.
* <tex>Z=\{z_{1}, ...\dots, z_{f}, ...\dots, z_{F}\}</tex> – {{---}} множество входных сигналов.
* <tex>W=\{w_{1}, ...\dots, w_{g}, ...\dots, w_{G}\}</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>.
* <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>a_{1}</tex> – {{---}} начальное состояние. АА работает в дискретные моменты времени, и в момент времени <tex>t=0</tex> автомат всегда находится в состоянии <tex>a_{1}</tex>.
}}
[[File:aa_work.png|300px|thumb|right|Рис. 1. Работа АААбстрактного автомата]]
Выходные сигналы АА зависят от того, что поступало на его вход раньше.
|}
В автоматах мура Мура выходные воздействия записаны на состояниях, а в автомате Мили — на переходах.
== Применение автоматов Мура и Мили ==
Также автоматы Мура и взаимодействующие автоматы Мили используются в генетическом программировании (например, для решения задачи об "Умном муравье"
<ref>[http://is.ifmo.ru/presentworks/_tsarev_sokolov2008/Vestnik/53/09-genetic-automata-smart-ant.ppt 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>р., выдает шоколадку и не возвращает сдачу.
== Способы задания автоматов ==
=== Графический способ задания автомата Мили ===
=== Табличный способ задания автомата Мура ===
=== Графический способ задания автомата Мура ===
== Реакция автоматов на входное слово ==
=== Автомат Мили ===
Реакцию автомата на входное слово <tex>\xi</tex> можно заменить обходом графа.
=== Автомат Мура ===
В рассматриваемом примере для автоматов Мили и Мура реакции автоматов на одинаковое входное слово совпадают, но они сдвинуты на один такт. Автоматы Мили и Мура дающие одинаковые реакции на одинаковые входные слова называются эквивалентными. Данное замечание приводит к задаче построения эквивалентных автоматов, дающих одинаковые реакции на одинаковые входные слова.
== Эквивалентность автоматов Мили и Мура ==
=== Переход от автомата Мура к автомату Мили ===
Шестикомпонентным набором с индексом А будем обозначать автомат Мура, а с индексом В – {{---}} автомат Мили.
Пусть задан автомат Мура (рис. 6).
[[File:aa_moor_ex3.png|300px|thumb|right|Рис.6 Автомат Мура]]
Требуется перейти к автомату Мили
=== Переход от автомата Мили к автомату Мура ===
Требуется перейти к автомату Мура
|-
| 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>
|}
При определении функции переходов результирующего автомата Мура из всех состояний, порожденных одним состоянием автомата Мили, должны быть переходы под воздействием одинаковых входных сигналов.
Поскольку в автомате Мура выходной сигнал зависит только от состояния автомата, то в примере рядом с состояниями проставим соответствующие выходные сигналы (рис. 8).
[[File:ex_2.png|300px|thumb|right|Рис. 8. Выходные сигналы автомата Мура]]
И так если осуществить следующие преобразования, то получим:
Можно утверждать, что если <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/>
*[http''Ожиганов А.А.'' Теория автоматов: Учебное пособие. СПб.: НИУ ИТМО, 2013 — С. 84.* ''Богаченко Н.Ф., Файзуллин Р.Т.'' Синтез дискретных автоматов://ofapУчебное пособие.ulstuОмск: Издательство Наследие.ru/vt/Theory_of_automats/part1Диалог-Сибирь, 2006.htm Абстрактные автоматы]*[https://ru.wikipedia.org/wiki/Автомат_Мура Википедия {{---}} Автомат Мура]*[http://windowofap.eduulstu.ru/resourcevt/007Theory_of_automats/79007/files/itmo1013part1.htm Ofap.pdf Теория автоматов]*[http://omgtuulstu.ru/general_information/faculties/radio_engineering_department/department_of_quot_integrated_protection_of_information_quot/files/teaching_materials/Sintez_diskretnyh_avtomatov.pdf Синтез дискретных автоматов{{---}} Абстрактные автоматы]*[http://www.kit-e.ru/articlesassets/plisfiles/pdf/2011_12_27.php pdf Николай Борисенко {{---}} Технические аспекты построения управляющих автоматов при проектировании цифровых устройств на основе современных ПЛИС]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
[[Категория: Другие автоматы]]
