Автомат мура и мили реферат

Обновлено: 02.07.2024

Изменения состояний цифрового автомата вызываются входными сигналами, которые возникают вне автомата и передаются в автомат по конечному числу входных каналов. В отношении входных сигналов цифровых автоматов принимаются два допущения: во-первых, для любого цифрового автомата число различных входных сигналов обязательно конечно, а, во-вторых, входные сигналы рассматриваются как причина перехода… Читать ещё >

Содержание

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

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

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

Необходимо рассмотреть такие вопросы как:

o Основные понятия теории автоматов

o Представление событий в автоматах

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

1. Основные понятия теории автоматов

Автомат называется конечным, если множество его внутренних состояний и множество значений входных сигналов конечные множества.

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

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

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

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

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

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

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

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

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

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

В отношении выходных сигналов вводятся допущения, аналогичные допущениям для входных сигналов. Во-первых, число различных выходных сигналов для любого цифрового автомата всегда конечно. Во-вторых, каждому отличному от нуля моменту автоматного времени относится соответствующий ему входной сигнал. Реальный физический выходной сигнал y (t), отнесенный к моменту времени t, появляется всегда после соответствующего этому же моменту времени входного сигнала x (t). Что же касается момента времени t перехода автомата из состояния q (t1) в состояние q (t), то сигнал y (t) может фактически появится либо раньше, либо позже этого момента.

В первом случае принимается, что выходной сигнал y (t) однозначно определяется входным сигналом x (t) и состоянием q (t1) автомата в предыдущий момент времени, во втором случае сигнал y (t) однозначно определяется парой (x (t), q (t)). Будем считать, что для любого момента времени всегда имеет место лишь одна из этих возможностей (одновременно для всех переходов).

Цифровые автоматы, в которых выходной сигнал y (t) определяется парой (x (t), q (t 1)), будем называть автоматами первого рода, а автоматы, в которых сигнал y (t) определяется парой (x (t), q (t)), автоматами второго рода.

Цифровой автомат (первого или второго рода) называется правильным, если выходной сигнал y (t) определяется одним лишь его состоянием (q (t 1) или q (t)) и не зависит явно от входного сигнала x (t).

Автоаты первого рода обычно называют автоматами Мили, а автоматы второго рода автоматами Мура.

o входного и выходного. Не интересуясь способом построения автомата, абстрактная

o теория изучает лишь те переходы, которые претерпевает автомат под воздействием

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

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

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

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

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

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

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

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

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

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

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

Для каждого автомата Мили может быть построен эквивалентный ему автомат Мура, и обратно — для каждого автомата Мура может быть построен эквивалентный ему автомат Мили.

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

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

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

[math]S_ = (A_, Z_, W_, \delta _, \lambda _, a_[/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_)[/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_), (a_, w_), (a_, w_)\>[/math]

[math]a_: A_ = \left \ < \begin (a_, w_) = b_ \\ (a_, w_) = b_ \\ \end \right.[/math]

[math]a_: A_ = \< (a_, w_) \> = b_[/math]

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

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

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

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

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

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

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

Тема контрольной работы по дисциплине "Прикладная теория цифровых автоматов" - "Абстрактные цифровые автоматы".

Цель работы - ознакомится с основными понятиями абстрактных цифровых автоматов; типами абстрактных автоматов; способами задания абстрактных автоматов; связью между моделями Мили и Мура; эквивалентными автоматами и эквивалентными преобразованиями автоматов; минимизацией числа внутренних состояний автомата и алгоритмом Ауфенкампа-Хона.

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

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

Общая теория автоматов подразделяется на абстрактную и структурную.

Абстрактная теория автоматов, отвлекаясь от структуры автомата (т.е. не интересуясь способом его построения), изучает лишь поведение автомата относительно внешней среды. Абстрактная теория автоматов близка к теории алгоритмов, являясь по существу ее дальнейшей реализацией.

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

Абстрактный цифровой автомат (ЦА) является математической моделью дискретного управляющего устройства.

Абстрактный ЦА определяется множеством, состоящим из шести элементов:

X=1 , x₂ ,. x_n > - множество входных сигналов (входной алфавит);

Y=1 , y₂ , y_m > - множество выходных сигналов (выходной алфавит);

А=< a₀ ,a₁ , a₂ ,. а_N > - множество состояний (алфавит состояний);

а_о - начальное состояние (а_о А);

- функция переходов автомата, задающая отображение (ХхА) А, т.е. ставящая в соответствие любой паре элементов декартового произведения (ХхА) элемент множества А;

- функция выходов автомата, задающая либо отображение (XxA) Y, либо отображение AY.

Иными словами, функция переходов показывает, что автомат S, находясь в некотором состоянии а_j А, при появлении входного сигнала х_j Х переходит в некоторое состояние а_р А. Это можно записать:

a_p = (a_i ,X_j ).

Функция выходов показывает, что автомат S, находясь в некотором состоянии а_j А, при появлении входного сигнала х_j Х выдает выходной сигнал у_k Y. Это можно записать: у_k = (a_i , X_j ).

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

Абстрактный автомат функционирует в дискретном автоматном времени t=0,1,2,. и переходы из состояния в состояние осуществляются мгновенно. В каждый момент tдискретного времени автомат находится в определенном состоянии a (t) из множества А состояний автомата, причем в начальный момент времени t=0 он всегда находится в начальном состоянии а_о . В момент времени t, будучи в состоянии a (t), автомат способен воспринять на входном канале сигнал х (t) X, и выдать на выходном канале сигнал y (t) = (a (t), x (t)), переходя в состояние a (t+1) = = (a (t),x (t)). Зависимость выходного сигнала от входного и от состояния означает, что в его составе имеется память.

По способу формирования функции выходов выделяют три типа абстрактных автоматов: автомат Мили, автомат Мура, С-автомат. Автомат Мили характеризуется системой уравнений:

y (t) = (a (t), x (t));

a (t+1) = δ (a (t), x (t)). (1-1)

Автомат Мура - системой уравнений:

y (t) = (a (t));

a (t+1) = δ (a (t), x (t)). (1-2)

С-автомат - системой уравнений:

у= y₁ y₂

y₁ (t) = (a (t),x (t));

У₂ (t) = ₂ (a (t));

Произвольный абстрактный автомат Мили или Мура (рис.1.1.) имеет один входной и один выходной каналы. Произвольный абстрактный С-автомат имеет один входной и два выходны х канала (рис.1.2.).

Рисунок 1.1 - Абстрактный автомат

Рисунок.1.2 Абстрактный С-автомат

Если на вход абстрактного автомата Мили или Мура, установленного в начальное состояние а_о , подавать буква за буквой некоторую последовательность букв входного алфавита х (0), х (1),. - входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита у (0), у (1),. - выходное слово. Для случая С-автомата на его выходах будут появляться две последовательности: y₁ (0), y₁ (1),. и y₂ (0), y₂ (1),. В абстрактном С - автомате выходной сигнал y₂ (t) = (a (t)) выдается все время, пока автомат находится в состоянии a (t). Выходной сигнал y₁ (t) =λ₁ (a (t),x (t)) выдается во время действия входного сигнала x (t) при нахождении С-автомата в состоянии a (t).

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

Выделяют полностью определенные и частичные автоматы.

Полностью определенным называется абстрактный цифровой автомат, у которого функция переходов или функция выходов, или обе эти функции определены для всех пар переходов (x_i ,a_j ).

Частичным называется абстрактный цифровой автомат, у которого функция переходов или функция выходов, или обе эти функции определены не для всех пар переходов (x_i ,a_j ).

Абстрактный цифровой автомат называется инициальным, если на множестве его состояний А выделяется начальное состояние а_о .

Чтобы задать конечный автомат S, необходимо описать все элементы множества: S=< X,A,Y,,,a_o >. Существует несколько способов задания работы автомата, но наиболее часто используется табличный (матричный), графический, аналитический.

При табличном способе автомат задается двумя таблицами: таблицей переходов и таблицей выходов, или матрицей соединений. Таблица переходов произвольного полностью определенного автомата строится следующим образом: строки таблицы помечаютсябуквами входного алфавита автомата, а столбцы таблицы - буквами алфавита состояний автомата; В клетке таблицы переходов, находящейся напересечении строки, отмеченной входным сигналом x_i , и столбца отмеченного состоянием a_j , ставится состояние а_k , являющееся результатом перехода автомата из состояния a_j под воздействием входного сигнала х_i , что определяется выражением a_k = (a_j , х_j ).

Таблица 1.1 Таблица переходов автомата

Пример заполнения таблицы переходов некоторого абстрактного полностью определенного автомата с входным алфавитом X=1 , х₂ > - и алфавитом состояний A=1 , a₂ , а₃ > представлен в табл.1.2.

ГОСТ

Автоматы Мили и Мура — это конечные автоматы, у которых выходные сигналы являются функциями входного сигнала и/или текущего состояния.

Введение

Электронные цифровые схемы с формальных позиций делятся на следующие классы:

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

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

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

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

В общем виде, без учёта различных подробностей, абстрактный автомат может быть представлен следующим образом:

Рисунок 1. Абстрактный автомат. Автор24 — интернет-биржа студенческих работ

Готовые работы на аналогичную тему

Эта иллюстрация схемы абстрактного автомата может быть в математических категориях представлена так:

Рисунок 2. Формула. Автор24 — интернет-биржа студенческих работ

Здесь использованы следующие обозначения:

Функции δ и λ не изображены на рисунке один с целью визуального упрощения. Подобный автомат должен работать дискретно по времени, то есть значения входов, выходов и внутреннее состояние автомата должны изменяться в определённые дискретные моменты времени. Примерами, описанных выше абстрактных автоматов, могут служить триггеры, регистры компьютеров или сумматоры.

Существует два основных типа абстрактных автоматов:

Автоматы Мили могут быть описаны следующей системой уравнений:

А автоматы Мура описываются такой системой уравнений:

Как следует из приведённых формул, состояние автомата c(t) в текущий момент времени выступает как функция его состояния в предыдущий момент времени и входного сигнала. Отличие этих двух автоматов заключается в виде функции выхода. В автомате Мили выходной сигнал должен определяться входным сигналом a(t) и состоянием автомата в предыдущий момент времени c(t-1). Выходной сигнал автомата Мура должен определяться входным сигналом a(t) и состоянием в данный момент c(t).

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

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

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

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

С помощью графов.
С помощью таблиц переходов и выходов.

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

Рисунок 3. Граф автомата Мили. Автор24 — интернет-биржа студенческих работ

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

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

Рисунок 4. Граф автомата Мура. Автор24 — интернет-биржа студенческих работ

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

Читайте также: