рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Цифровых автоматов Мили и Мура

Цифровых автоматов Мили и Мура - раздел Транспорт, Теория цифровых автоматов Абстрактный Цифровой Автомат Работает Как Преобразователь Слов Входного Алфав...

Абстрактный цифровой автомат работает как преобразователь слов входного алфавита в слово в выходном алфавите [5]. Рассмотрим это положение, взяв в качестве примера автомат Мили S1.

На вход этого автомата, установленного в начальное состояние a1, поступает шестибуквенное (шеститактное) слово x=z1z1z2z1z2z2.

Проследив по таблицам переходов и выходов или непосредственно по графу поведение цифрового автомата S1, опишем его тремя сроками, первая из которых соответствует входному слову x, вторая - последовательности соответствующих этому слову состояний b, третья - выходному слову w, которое появляется на выходе автомата.

w = l(a1, x) - реакция автомата Мили в состоянии a1 на входное слово x.

Как видно из этого примера, в ответ на входное слово длиной k символов автомат Мили S1 выдаёт последовательность состояний длины k+1 символов и выходное слово длиной k символов.

В общем виде поведение автомата Мили, установленного в состояние am, можно описать следующим образом:

входное слово zi1 zi2 zi3

последовательность am ai2=d(am, zi1) ai3=d(ai2, zi2)

состояний

выходное слово wi1=l(am, zi1) wi2=l(ai2, zi2) wi3=l(ai3, zi3).

Точно так же описывается поведение автомата Мура, находящегося в состоянии am, при приходе входного слова zi1, zi2, ... , zik. Учитывая, что выходной сигнал автомата Мура в момент времени t, то есть w(t), зависит лишь от состояния, в котором находится автомат в момент t, то есть от a(t), получим:

Выходной сигнал wi1=l(am) в момент времени i1 не зависит от входного сигнала zi1, а определяется только состоянием am. Таким образом, выходной сигнал wi1 не связан с входным словом, поступающим на вход автомата, начиная с момента i1.

По этой причине реакцией автомата Мура, установленного в состояние am, на входное слово x = zi1, zi2, ... , zik является выходное слово той же длины k, с исключением первого символа выходного слова:

w = l(am, x) = wi2, wi3, ... , wi(k+1).

В качестве примера рассмотрим автомат Мура S5 , граф которого изображён на рис.26, и определим его реакцию в начальном состоянии a1 на то же самое слово x=z1z1z2z1z2z2 , которое использовалось для оценки поведения автомата Мили S1.

Часть выходного слова, выделенная штриховой рамкой, является реакцией автомата Мура на входное слово.

Таким образом, реакции автоматов S5 и S1 в начальном состоянии на входное слово x с точностью до сдвига на один такт совпадают. Эти автоматы являются эквивалентными.

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

При рассмотрении алгоритмов взаимной трансформации автоматов Мили и Мура, в соответствии с изложенным выше, всегда будем пренебрегать в автоматах Мура выходным сигналом, связанным с начальным состоянием, то есть функцией l(a1).

Рассмотрим преобразование автомата Мура в эквивалентный ему автомат Мили.

Исходный автомат Мура

SA = {AA, XA, YA, dA, lA, a1A}

где: AA= {a1, ... , am, ... , aM} , XA= {z1, ... , zf, ... , zF}, YA= {w1, ... , wg, ... wG},

dA: AA´XA®AA, lA=AA®YA, a1A=a1 - начальное состояние.

Эквивалентный ему автомат Мили

SB ={AB, XB ,YB, dB, lB, a1B},

имеющий

AB = AA; XB= XA; YB= YA; dB=dA; a1B= a1A.

Для SB функция выходов lB определяется иначе, чем для исходного автомата Мура SA. Если в исходном автомате Мура lA(as)= wg, то в эквивалентном автомате Мили lB(am, zf)= wg.

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

При использовании табличного описания автомата Мура SA, таблица переходов автомата Мили SB совпадает с таблицей переходов SA, а таблица выходов SB получается из таблицы переходов заменой символа as, стоящего на пересечении строки zf и столбца am, символом выходного сигнала wg, отмечающего столбец as в таблице переходов автомата SA.

Пример трансформации автомата Мура S3 (таблица 21) в автомат Мили S6 приведён на рис.28 и в таблице 23 и таблице 24.

 

Отмеченная таблица переходов автомата Мура S3

 

Выделение совмещённой таблицы переходов и выходов автомата Мили S6

 

 

По процедуре построения автомата Мили SB видно, что он эквивалентен автомату Мура SA.

Действительно, если некоторый входной сигнал zf ÎX поступает на вход автомата SA, находящегося в состоянии am, то он перейдёт в состояние as = dA(am, zf) и выдаст выходной сигнал wg = lA(as). Соответствующий эквивалентный автомат Мили SB из состояния am также перейдёт в состояние as, поскольку dB(am, zf) = dA(am, zf) = as и выдаст тот же выходной сигнал wg согласно способу построения функции lB . Таким образом, любое входное слово конечной длины, поданное на входы автоматов SA и SB, установленных в состояние am, вызовет появление одинаковых выходных слов и, следовательно, автоматы SA и SB эквивалентны.

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

Преходящим называется состояние, в которое, при представлении автомата в виде графа, не входит ни одна дуга, но которое имеет, по крайней мере, одну выходящую дугу (например - состояние a1 автомата S2 на рис.23).

Рассмотрим преобразование автомата Мили в эквивалентный ему автомат Мура.

Исходный автомат Мили

SA = {AA, XA, YA, dA, lA, a1A}

где: AA= {a1, ... , am, ... , aM} , XA= {z1, ... , zf, ... , zF}, YA= {w1, ... , wg, ... wG}, dA реализует отображение AA´XA в AA, то есть dA: AA´XA®AA и lA=AA®YA, a1A=a1 - начальное состояние.

Эквивалентный ему автомат Мура

SB ={AB, XB ,YB, dB, lB, a1B},

имеющий

XB= XA; YB= YA.

Для определения AB каждому состоянию as Î AA поставим в соответствие множество AS всевозможных пар вида (as, wg), где wg - выходной сигнал, приписанный входящей в as дуге. Это положение иллюстрируется примером преобразования фрагмента автомата Мили на рис.29.

Множество состояний автомата SB, получим как объединение множеств AS (S = 1, ... ,M):

.

Для определения функций выходов lB, каждому состоянию эквивалентного автомата Мура, представляющего собой пару вида (as, wg), поставим в соответствие выходной сигнал wg. Если в автомате Мили SA, был переход dA(am, zf) = as и при этом выдавался выходной сигнал lA(am, zf)= wk, то в эквивалентном автомате Мура SB (рис.30) будет переход из множества состояний Am, порождаемых am, в состояние (as, wk) под действием того же входного сигнала zf.

Как начальное состояние a1B можно взять любое состояние из множества A1, порождаемого начальным состоянием a1 автомата SA.

При последующем сравнении реакций эквивалентных автоматов SA и SB на всевозможные входные слова не должен учитываться выходной сигнал в момент t = 0, связанный с состоянием a1B автомата Мура SB.

Рассмотрим пример преобразования автомата Мили S1, изображённого в виде графа на рис.22 и описанного в таблице 18.

A1 = {(a1,w1),(a1,w2)} = {b1,b2}, где b1 = (a1,w1) b2 = (a1,w2). A2 = {(a2,w1)} = b3.

A3 = {(a3,w1),(a3,w2)} = {b4,b5}, где b4 = (a3,w1) b5 = (a3,w2).

Тогда = {b1, b2, b3, b4, b5}. С каждым состоянием, представляющим теперь пару, свяжем выходной сигнал, являющийся вторым элементом этой пары:

lB(b1) = lB(b3) = lB(b4) = w1; lB(b2) = lB(b5) = w2.

В качестве начального состояния можно выбрать любое из множества A1. Таким образом строится отмеченная таблица выходов эквивалентного автомата Мура. Оказывается, что это автомат S5, граф которого ранее изображён на рис. 26.

 

Рассмотрим преобразование автомата Мили в эквивалентный автомат Мура с учётом ранее введённого ограничения на присутствие преходящих состояний. Для примера возьмём автомат Мили S7, граф которого приведён на рис.31.

b2 = (a2, w1); b3 = (a2, w2); b4 = (a3, w1); b5 = (a3, w2); b1 = (a1, - ).

Преходящее состояние в автомате Мили порождает состояние с неопределённым выходным сигналом в эквивалентном автомате Мура.

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

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

– Конец работы –

Эта тема принадлежит разделу:

Теория цифровых автоматов

Южно-уральский государственный университет..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Цифровых автоматов Мили и Мура

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Базис И, ИЛИ, НЕ. Свойства элементарных функций алгебры логики
  Пусть x - некоторая логическая переменная. Тогда: 1. , что означает возможность исключения из логического вы

Табличное описание булевых функций
  Вследствие конечности множества наборов заданного количества логических переменных, простейшим и самым естественным способом описания ФАЛ является табличный. Пример описания трёх ФА

Аналитическое описание булевых функций
На примерах описания ФАЛ, приведенных в таблице 3, видно, что конституента 1 может быть описана в виде элементарной конъюнкции переменных:

Геометрическое представление булевых функций
  В геометрическом представлении ФАЛ значения входных переменных n - местного набора интерпретируются как координаты в n - мерной декартовой системе координат. Координат

Минимизация с помощью минимизирующих карт
  Как было отмечено выше, одним из способов представления ФАЛ от небольшого числа переменных (обычно не больше 5) являются диаграммы Карно или Вейча, которые строятся на развёртках мн

Минимизация функций алгебры логики по методу Квайна
  При минимизации по методу Квайна в базисе И, ИЛИ, НЕ исходная ФАЛ задаётся в СДНФ. Целью минимизации является нахождение всех первичных импликант и выбор некоторых из них для

По методу Квайна - Мак-Класки
  Недостаток метода Квайна - необходимость исчерпывающего попарного сравнения или сопоставления всех минтермов на этапе нахождения первичных импликант. С ростом числа минтермов увелич

Логические элементы И и И-НЕ
(Позитивная логика) Схема логического элемента И, построенного на полупроводниковых диодах и резисторе, приведена на рис.10а).

Логические элементы ИЛИ, ИЛИ-НЕ
  Схема логического элемента ИЛИ, построенного на полупроводниковых диодах и резисторе, приведена на рис.12а).

Программируемые логические матрицы (ПЛМ)
  Программируемая логическая матрица [2] представляет собой функциональный блок, созданный на базе интегральной полупроводниковой технологии и предназначенный для реализации логически

Процедуры программирования ПЛМ
Физическим принципом программирования ПЛМ является пережигание (испарение) выбранных перемычек. В процессе эксплуатации ПЛМ могут возникнуть следующие задачи: - начальное программ

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

Методы описания цифровых автоматов
  Чтобы задать цифровой автомат S, необходимо описать все элементы множества S = { A, X ,Y, d, l, a1}, то есть входной и выходной алфавиты и алфавит состояний, а также функ

Синхронные и асинхронные цифровые автоматы
Состояние as автомата S называется устойчивым состоянием, если для любого входа zfÎX, такого, что d(am, zf) = as, имеет место d(as

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

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

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

Синхронизация в цифровых автоматах
  Смена состояний в синхронизированных автоматах происходит в определённые моменты времени, задаваемые по цепям синхронизации внешним тактовым генератором. Изменение состояний в реаль

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

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

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

Принцип действия управляющего автомата с хранимой в памяти логикой и микропрограммное управление
  Хранимая в памяти микропрограмма должна содержать информацию о функциях переходов и выходов управляющего микропрограммного автомата. Рассматривая управляющий автомат (УА) в терминах

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

Вертикальное микропрограммирование
  При вертикальном микропрограммировании микрооперация определяется не состоянием одного из бит микрокоманды, а двоичным кодом, содержащимся в операционной части микрокоманды (

Горизонтально - вертикальное микропрограммирование
  В этом случае подмножества VL представляются горизонтальным способом , а микрооперации внутри каждого из подмножеств - вертикальным способом (рис.66). Для каждого подмнож

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

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

Синтез микропрограммного автомата Мура
Синтез автомата Мура по граф - схеме алгоритма также состоит из двух этапов: - получение отмеченной ГСА; - построение графа автомата. На первом из этих этапов начальная,

Минимизация микропрограммных автоматов
  Изложенный ранее метод минимизации абстрактных автоматов применяется и для минимизации полностью определённых микропрограммных автоматов. Если два состояния автоматы Мили с

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги