Автомат мура как построить

1.5. Автоматы Мура

Определение. Автоматом Мура называют набор А= (Х, Z, Q, F, G), в котором:

1) Х = (Х₁,Х₂,…,Х_N) – множество возможных входов,

2) Z = (Z₁,Z₂,…,Z_M) – множество возможных выходов,

3) Q = (Q₁,Q₂,…,Q_Р) – множество возможных внутренних состояний,

4) F : Q Z — функция выходов,

5) G : х q q — функция переходов.

Как следует из определения, отличие автомата Мура от автомата Мили заключается в том, что выход у него фор-мально не зависит от входа, а только от внутреннего со-стояния автомата. Однако в общем случае неявная зависи-мость выходов Z от входов Х присутствует, поскольку Z зависит от внутренних состояний Q, а Q — в свою очередь — от входов Х .

Пример 1. Наиболее распространенным автоматом Мура является автономный светофор, в котором переклю-чение цветов “красный – желтый – зеленый – желтый — …”

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

Отметим, что в приведенном примере у автомата отсутствует вход.

Для задания автоматов Мура используют те же спосо-бы, что и для автоматов Мили. При этом на графе пере-ходов значения выходов проставляют внутри либо рядом с вершинами, обозначающими состояния автомата.

Пример 2. Построить граф переходов и таблицу со-стояний для автономного светофора.

Решение. Выходной информацией, выдаваемой устройст-вом, являются световые сигналы красного, зеленого и жел-того цвета. Обозначим их, соответственно, К,З,Ж. Внут-ренние состояния, соответствующие красному и зеленому цвету, обозначим через q_к и q_з. Поскольку желтый цвет дол-

жен зажигаться дважды при разных внутренних состояни-

ях, для него отводим два состояния: q_жк и q_жз, соответ-ствующие желтому цвету, включаемому после красного и после зеленого цветов. Искомый граф переходов имеет вид, показанный на Рис.5.10.

Таблица состояний имеет вид:

Q_j (t_i)

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

Для любого автомата Мили А = (Х,Z,Q,F,G) существу-ет эквивалентный ему автомат Мура А = (Х,Z,Q,F,G) .

Доказательство. Обозначим: Х=N, Z=M, Q=P.

Укажем способ построения эквивалентного автомата Мура. Множества входов и выходов его примем такими же, как и у исходного автомата Мили: Х =Х, Z =Z. Множество внутренних состояний построим состоящим из двух частей: Q= QQ д , где Q — множество состояний автомата Мили, Q д =< Q д _ij; i=1,…,P;j=1,…,N>– множество дополнительных состояний, Q д =P N.

Определим функцию переходов автомата Мура G следующим способом:

а) на множестве Q (в момент времени t₁)

G (Q_i,Х_j)= Q д _ij;

б) на множестве Q д (в моменты времени t₂, t₃ , …)

G (Q д _ij ,Х_k)= Q д _lk; где Q_l = G(Q_i ,Х_k) .

Таким образом, в момент времени t₁ происходит пере-ход из подмножества состояний Q (в котором задано на-чальное состояние автомата) в подмножество Q д , где осуществляется его последующее функционирование. Ин-формация о текущем состоянии автомата Мили запоминает-

ся в первом индексе дополнительного состояния автомата Мура, информация о текущем входе – во втором индексе. За счет этого дополнительные состояния Q д автомата Мура содержат полную информацию о внутреннем состоянии и входе автомата Мили в каждый момент времени.

Функция выходов автомата Мура может быть задана таким способом:

а) F(Q_i) — не определено, поскольку данные состояния при срабатывании F не достижимы (в момент времени t₁проис-ходит переход из Q в Q д и дальнейшая работа осуществ-ляется в данном подмножестве состояний);

б) F( Q д _ij )= F ( Q_i, Х_j) .

Эквиваленность автоматов А и А следует из способа задания функций переходов и выходов F и G.

Пример 3. Построить автомат Мура, эквивалентный сокращенному автомату Мили, построенному в Примере 2 п.1.4.

Решение. Задаем множества входов, выходов и внутренних состояний:

Х = Х =(a, b); Z=Z=(x, y, z);

Q =QQ д =( Q₁, Q₂)  ( Q₁₁, Q₁₂, Q₁₂, Q₂₂).

Определяем функцию переходов на множестве Q :

G (Q₁, a) = Q д ₁₁; G (Q₁, b) = Q д ₁₂;

G (Q₂, a) = Q д ₂₁; G (Q₂, b) = Q д ₂₂.

Определяем функцию переходов на дополнительном множестве Q д :

G (Q₁₁,a) = Q д ₂₁, т.к. Q₂ = G(Q₁, a) ;

G (Q₁₁,b) = Q д ₁₂, т.к. Q₁ = G(Q₁, b) ;

G (Q₁₂,a) = Q д ₂₁, т.к. Q₂₁ = G(Q₁, a) ;

G (Q₁₂,b) = Q д ₁₂, т.к. Q₁ = G(Q₁, b) ;

G (Q₂₁,a) = Q д ₁₁, т.к. Q₁ = G(Q₂, a) ;

G (Q₂₁,b) = Q д ₂₂, т.к. Q₂ = G(Q₁, b) ;

G (Q₂₂,a) = Q д ₁₁, т.к. Q₁ = G(Q₁, a) ;

G (Q₂₂,b) = Q д ₂₂, т.к. Q₂ = G(Q₁, b) .

а) на множестве Q — не определена,

б) на множестве Q д :

F(Q₁₁)= F(Q₁,a)=z;

F(Q₁₂)= F(Q₁,b)=z;

F(Q₂₁)= F(Q₂,a)=x;

F(Q₂₂)= F(Q₂,b)=y.

Граф переходов построенного автомата Мура дан на Рис. 5.11.

По аналогии с автоматами Мили для автоматов Мура вводят понятия реакций и сокращенного атвомата.

1. Построить автомат Мура по автомату Мили, заданному в Задаче I.3 п.1.4 графом переходов (Рис.5.8).

Автоматы Мура и Мили

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

В каждый момент времени АА, будучи в состоянии [math]a_^[/math] , способен воспринимать одну из букв входного алфавита [math]z_^[/math] . В соответствии с функцией [math]\delta[/math] , АА перейдет в состояние [math]a_<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_[/math] .

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

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

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

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

Выход автомата в каждом состоянии определяется парой [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] .

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

В качестве примера применения автомата Мили рассмотрим автомат по продаже шоколадок стоимостью [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_[/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] рублей, то происходит следующее:

Автомат переходит в состояние [math]10[/math] р. и ничего не выдает;

Автомат переходит в состояние [math]15[/math] р. и ничего не выдает;

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

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

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

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

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

[math]a_[/math]

[math]z_[/math] [math]a_~~[/math]~~ [math]=\delta (a_, z_)[/math]

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

[math]a_[/math]

[math]z_[/math] [math]w_[/math] [math]=\lambda (a_, z_)[/math]

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

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

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

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

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

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

[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 выходных сигнала.

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

Автомат Мили

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

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

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

Автомат Мура

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

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

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

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

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

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

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

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

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

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

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

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

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

Мура Мили

[math]\delta _ (a_, z_) = a_~~[/math]~~ [math]\delta _ (a_, z_) = a_~~[/math]~~

[math]\lambda _(a_) = w_[/math] [math]\lambda _ (a_, z_) = w_[/math]

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

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

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

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

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

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

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

Мура Мили

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

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

Мура Мили

[math]A_ ~~= \<(a_~~, w_<1>), (a_~~, w_<2>), (a_~~, w_<3>)\>[/math]~~~~~~~~

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

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

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

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

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

Мили Мура Мили

[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] (т.е. эквивалентность обладает свойством транзитивности).

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

Самостоятельное изучение схемотехники. Абстрактный автомат. Часть 2

Статья написана, собрана и сверстана Brotherofken. Спасибо ему огромное.
В предыдущей статье я попытался изложить все основные определения и принципы, чтобы сделать эту статью максимально понятной. Все не уместилось, так что я настоятельно советую ознакомиться с этими файлами:
Базис, Базис2, Минимизация. Далее в этой статье я оставил несколько разъясняющих пометок курсивом.

В этой статье я попробую объяснить доступным языком что такое абстрактный автомат, способы его представления. Так как теория автоматов полна математики и сложна, постараюсь писать человеческим языком, чтобы неподготовленный читатель смог понять о чём идёт речь.

Комбинационные Схемы (КС) – не обладают памятью. Выходной сигнал формируется в зависимости от комбинации входных данных в фиксированный момент времени (учитывая задержку на преобразования сигналов).Комбинационные схемы, их типы и принципы построения могут быть темой для отдельной статьи, а в качестве примеров можно привести: Управляемые шины, мультиплексоры и демультиплексоры, дешифраторы и шифраторы, преобразователи кодов, комбинационные счетчики и сумматоры и т. д.

Схемы с памятью – алгоритм их работы зависит от состояния входов и памяти (того, что было в предыдущие моменты времени). Эти схемы описываются с применением теории конечных автоматов. Речь о них и пойдёт далее.

Абстрактный автомат

Автомат должен будет реализовывать некоторые функции, которые заданы разработчиком. Он может быть простым сумматором, может реализовывать какую-либо микрокоманду процессора, выбирать слова из оперативной памяти или заниматься синтаксическим анализом выражения.
В общем виде, не вдаваясь в подробности, абстрактный автомат можно представить следующим образом:

Или, если перейти от иллюстрации к математическому описанию:
A = <A, B, C, δ, λ>

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

Множество – представляет собой множество значений на физических выходах автомата.

Множество – а множество, которое представляет внутреннее состояние автомата – память. На будущее C0 будем обозначать начальное состояние автомата.

δ = X × Z → Z – это функции переходов автомата, они однозначно определяют состояние ai в которое переходит автомат из состояния aj.

λ = X × Z → Y – функции выходов, они определяют что находится на выходе автомата в зависимости от входов и внутреннего состояния.

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

Автоматы Мили. Описывается системой уравнений:
c(t) = δ( a(t), c(t-1) );
b(t) = λ( a(t), c(t-1) ).

Автоматы Мура. Описывается уравнениями:
c(t) = δ( a(t), c(t-1) );
b(t) = λ( a(t), c(t) ).

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

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

Как мы выяснили в первой части — автомат представляет собой совокупность входного и выходного алфавитов, множества внутренних состояний и функций, определяющих переходы и выходы. Однако, обычно функции δ и λ не заданы, и поведение автомата приходится описывать по-другому.

При помощи графов.

При помощи таблиц переходов и выходов.

Графы

Граф автомата – это ориентированный связный граф, вершины которого символизируют внутренние состояния автомата, а дуги – переходы из одного состояния в другое.

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

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

Важный момент: Если из каждой вершины выходит столько дуг, сколько есть входных букв, то автомат называется полным. Другими словами – если из каждой вершины определены переходы для каждой входной буквы. В наших примерах автомат Мили является полным, а автомат Мура – частичным.
И ещё: Если из одной вершины выходит дуг больше, чем входных букв (то есть 2 и более дуг с одинаковыми входными буквами), то такой автомат называется недетерминированным. Такое может произойти при построении формализованного описания и тогда надо будет произвести переход к детерминированному автомату, но это не всегда можно выполнить. Описание этого процесса я тоже упускаю, сразу нарисовав детерминированный автомат.
На этом о графах всё.

Таблицы переходов и выходов.

Графы нагляднее для человека, а таблицы — для машины. Любой автомат можно представить в виде таблицы переходов и выходов (ТПВ). В ТПВ строками являются внутренние состояния автомата, а столбцами – входные буквы.
Построим ТПВ для наших графов Мили и Мура. Если не определена какая-либо входная или выходная буква, то вместо неё ставится прочерк. Если не определено состояние, то действует это же простое правило.

ТПВ графа Мили

В ТПВ Мили в каждой клетке записаны переходы и выходы. Например, если автомат находится в состоянии С0 и на вход приходит буква a1, то он перейдёт в состояние С1 и на выходе появится буква b3.

ТПВ графа Мура

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

Пример синтеза автомата

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

Кодируем входной и выходной алфавиты:
A = , где a0 – логическая 1 на входе R, a1 – логическая единица на входе S.
B = , где b0 – логический 0 на выходе Q, b1 – логическая единица на выходе Q.
Строим граф автомата Мили:

Вот такая забавная чебурашка получилась :-). Теперь можно построить таблицу переходов и выходов:

Если расписать эту таблицу преобразовав условные обозначения в фактические, то получим таблицу которая представляет из себя таблицу переходов триггера. Затем её можно упростить:

Нанесём полученную функцию на карту Вейча и минимизируем:

Выпишем, что получилось:

Строим по функции схему (Выполняли домашнее задание?):

Немного непривычно видеть триггер в булевом базисе, поэтому переведём функцию в базис И-НЕ и нарисуем схему в нём:

А на схеме асинхронный RS триггер обозначается вот так:

Теперь если приложить немного старания, то можно самостоятельно синтезировать простую новогоднюю гирлянду.

Построение абстрактных автоматов по граф-схеме микропрограммы

Переход осуществляется так же в два этапа. На первом этапе производится определение числа состояний путем разметки и отметки граф -схемы; на втором — определение графа автомата.

Символом помечаем начальную и конечную вершины ГСА микропрограммы .

Символами $а_2, а_3, а_4,\dots$ помечаем операторные вершины, (рис.4.7,б).

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

В результате анализа разметки видим, что между парами меток имеем пути второго и третьего вида. Каждому пути ставим соответствующий переход.

Построение автомата Мура рассмотрим на примере ГСА МП, представленной на рис.4.8.

На первом этапе выполним разметку согласно указанным выше правилам. Получаем шесть меток (рис.4.8).

На втором этапе строим граф автомата Мили. Имеем шесть вершин графа соответствующих шести состояниям. Внутри каждой вершины записываем соответствующий выходной сигнал.

По ГСА находим все пути между соседними метками. Так из метки в метку существует один путь третьего типа, то есть безусловный переход . Этот путь изображается дугой перехода из состояния в состояние .

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

4.3 Абстрактный С-автомат (совмещенный автомат)

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

$\lambda : A \times Z\to W (w_s= \lambda (a_m, z_i)/ a_s \in A, w \in W),$

В автомате Мура выходной сигнал зависит только от состояния, и выдается все то время, когда автомат находится в этом состоянии (рис.4.10,б):

$\lambda : A \to W (w_s= \lambda (a_m)/ a_s \in A, w \in W),$

Совмещенный автомат или — автомат таким образом содержит сигналы как первого рода, так и второго и описывается восьмеркой вида:

$S=\lbrace A, Z, W, U, \delta, \lambda_1, \lambda_2, а_1 \rbrace,$

где $A=\< a_1, a_2, a_3,\dots ,a_m\>» /> — множество состояний автомата;</p> <p><img decoding=$

$\lambda_1 : A \times Z \to W ( w_g= \lambda_1( a_m, z_f) | a_s \in А, w_g \in W );$

$\lambda_2 : A \to U ( u_h= \lambda_2( a_m) | u_h \in U );$

$a1 \in А$

При графическом задании — автомата на переходах указываются выходные сигналы 1 рода , а в вершинах выходные сигналы 2 рода (рис.4.11).

Явное задание — автомата требует описание всех составляющих и выполняется так же как и для автоматов Мили и Мура.

Табличное задание — автомата состоит в представлении работы автомата двумя таблицами: таблицей переходов (табл.4.1) и таблицей выходов (табл.4.2), в которой в отличие от автомата Мили в верхней строке добавляются сигналы второго рода.

Таблица 4.1.

z\a a₁ a₂ a₃

z₁ a ₃ a ₁ a ₁

z₂ a₁ a₃ a₂

Таблица 4.2.

\u_h u₁ u₃ u₂

z\a a₁ a₂ a₃

z₁ w₁ w₁ w₂

z₂ w₁ w₂ w₁

Матричное задание — автомата состоит в описании двумя матрицами аналогично матричному представлению автоматов Мили и Мура.

$C= \left|\left|\begin<array> <ccc>z_2/\omega_1& -& z_1/\omega_1 \\ z_1/\omega_1& — & z_2/\omega_2 \\ z_2/\omega_2& z_1/\omega_1& — \end<array>\right|\right|, W= \left|\left|\begin<array> <c>u_1 \\ u_3 \\ u_2 \end<array>\right|\right|» /></p> <div style=$
Читать:
Где купить лампочку на 36 вольт