Абстрактные цифровые автоматы - Коммуникации, связь, цифровые приборы и радиоэлектроника контрольная работа

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


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Тема контрольной работы по дисциплине "Прикладная теория цифровых автоматов" - "Абстрактные цифровые автоматы".
Цель работы - ознакомится с основными понятиями абстрактных цифровых автоматов; типами абстрактных автоматов; способами задания абстрактных автоматов; связью между моделями Мили и Мура; эквивалентными автоматами и эквивалентными преобразованиями автоматов; минимизацией числа внутренних состояний автомата и алгоритмом Ауфенкампа-Хона.
Пример заполнения таблицы переходов некоторого абстрактного полностью определенного автомата с входным алфавитом X={х 1 , х 2 } - и алфавитом состояний A={a 1 , a 2 , а 3 } представлен в табл.1.2.
Если абстрактный автомат частичный, то в клетке таблицы его переходов, находящейся, на пересечении строки, отмеченной входным сигналом и столбца отмеченного соответствующим состоянием (при условии, что переход в это состояние под действием данного входного сигнала не определен) ставится прочерк, и любое входное слово, приводящее к указанному переходу является запрещенным.
Заполнение остальных клеток аналогично случаю полностью определенного автомата. Вид таблицы переходов не зависит от типа задаваемого автомата (автомат Мили, Мура, С-автомат). Таблицы выходов автоматов Мили, Мура, С-автомата имеют различия.
Таблица выходов полностью определенного автомата Мили строится следующим образом: идентификация столбцов и строк, а также формат таблицы соответствуют таблице переходов полностью определенного автомата. В клетке таблицы выходов, находящейся на пересечении строки, отмеченной входным сигналом X j , и столбца, отмеченного состоянием а к , ставится выходной сигнал У m , который автомат выдает, находясь в состоянии а k при наличии входного сигнала Xj, что определяется выражением Ym= (а k , х j ).
Таблица 1.3 Таблица выходов абстрактного автомата Мили.
Пример заполнения таблицы выходов некоторого абстрактного полностью определенного автомата с входным алфавитом X={x 1 , x 2 }, алфавитом состояний A={a 1 , а 2 , а 3 } и выходным алфавитом Y={y 1 , y 2 , y 3 }-представлен в табл.1.4.
Таблица выходов полностью определенного автомата Мура строится более просто: каждому состоянию автомата ставится в соответствие свой выходной сигнал. Пример таблицы выходов автомата Мура с алфавитом состояний A={a 1 , а 2 , а 3 } и выходным алфавитом Y={y 1 , y 2 , у 3 } представлен в таблице 1.5.
Очевидно, абстрактный полностью определенный С-автомат задается двумя таблицами выходов, первая из которых есть таблица выходов автомата Мили, а вторая - Мура. Если автомат частичный, то в некоторых клетках его таблицы может стоять прочерк, что означает отсутствие выходного сигнала.
На практике таблицы переходов и выходов часто совмещают в одну таблицу, называемую отмеченной таблицей переходов автомата. Примеры отмеченных таблиц переходов представлены в табл.1.6. - 1.8 (Общий вид отмеченной таблицы переходов - табл.1.6., отмеченная таблица переходов автомата Мили - табл.1.7., отмеченная таблица переходов автомата Мура - табл.1.8.).
Кроме рассмотренных выше таблиц переходов и выходов произвольный абстрактный автомат может быть задан матрицей соединений.
Матрица соединений является квадратной и содержит столько столбцов (строк), сколько различных состояний содержит алфавит состояний данного автомата. Каждый столбец (строка) матрицы соединений помечается буквой состояния автомата. В клетке, находящейся на пересечении столбца, помеченного буквой а j и строки, помеченной буквой a s автомата, ставится входной сигнал (или дизъюнкция входных сигналов), под воздействием которого осуществляется данный переход.
Для абстрактного автомата Мили в клетке рядом с состоянием проставляется также выходной сигнал, который автомат выдает в результате данного перехода (табл.1.9.) Для автомата Мура выходной сигнал проставляется в строке рядом с состоянием (эти состояния соответствуют исходным состояниям автомата).
При графическом способе задания абстрактные автоматы представляются ориентированными графами. Графом автомата называется ориентированный связный граф, вершины которого соответствуют состояниям автомата, а дуги между ними - переходам между состояниями. Две вершины a k и a s соединяются дугой в том случае, если в автомате имеется переход из состояния a k в состояние a s . Для автомата Мили входной и выходной сигналы проставляются на дуге, соответствующей данному переходу (рис 1.3.), для автомата Мура входной сигнал проставляется на дуге, а выходной - рядом с вершиной, соответствующей состоянию (рис 1.4.).
Здесь рассматриваются только детерминированные автоматы, у которых выполнено условие однозначности переходов: автомат, находящийся в некотором состоянии, под действием любого входного сигнала не может перейти более чем в одно состояние. Применительно к графическому способу задания автомата это означает, что в графе автомата из любой вершины не могут выходить две и более дуги, отмеченные одним и тем же входным сигналом.
Рисунок 1.3-Граф автомата Мили Рисунок 1.4-Граф автомата Мура
При аналитическом способе задания абстрактные автоматы задаются четверкой объектов:
S={ X,A,Y,F}, где F задает для каждого состояния а j автомата отображение (ХхА) - > (AxY). Другими словами, при аналитическом способе задания для каждого состояния автомата а j указывается отображение F ai , представляющее собой множество всех троек а р , x m , y k , и таких, что под воздействием входного сигнала x m автомат переходит из состояния а j в состояние а р , выдавая при этом выходной сигнал y k .
Применительно к общему определению абстрактного автомата, последнее равнозначно описанию функций д и л в соответствии с выражением: a p = д (a i , x m ), y к = л (a i , x m ).
Отображение F ai записывается следующим образом:
F ai {a p (X m /y k ),a i (X f /y z ) …}.
Для абстрактного автомата Мили (табл.1.7.) аналитическое задание имеет следующий вид:
S={ X,A,Y,F}, X={x 1 ,x 2 }, A={a 1 , а 2 , а 3 }, Y={y 1 , y 2 , у 3 },
F a1 ={a 2 (x 1 /y 2 ), a 1 (x 2 /у 3 ) },
F а 2 ={а 3 (x 1 /y 3 ), a 1 (x 2 /y 1 ) },
F a 3 ={a 1 (x 1 /y 3 ), а 2 (x 2 /y 2 ) }.
Следует отметить, что функция F ai всегда записывается для исходного состояния.
Определим синхронные и асинхронные автоматы. Состояние а s автомата S называется устойчивым cостоянием, если для любого входного сигнала х j Х, такого, что а s = д (а i Х m ) имеет место a s = д (a s , x m ).
Автомат S называется асинхронным, если каждое его состояние a s А устойчиво. Автомат S называется синхронным, если он не является асинхронным.
Необходимо заметить, что построенные на практике автоматы всегда асинхронные и устойчивость их состояний всегда обеспечивается тем или иным способом, например, введением сигналов синхронизации. Однако, на уровне абстрактной теории автоматов, когда автомат всего лишь математическая модель, которая не отражает многих конкретных особенностей его реализации, часто оказывается более удобным оперировать с синхронными автоматами.
Точно так же можно описать поведение автомата Мура, находящегося в состоянии a m , при приходе входного слова x i 1 , x i2 ,., х ik . Напомним, что в соответствии с (1-2) выходной сигнал в автомате Мура в момент времени t (У (t)) зависит лишь от состояния, в котором находится автомат в момент t (a (t)):
Очевидно, что выходной сигнал у i 1 =л (a m ) в момент времени i 1 не зависит от входного сигнала x i 1 , а определяется только состоянием а m .
Таким образом, этот сигнал y i 1 никак не связан с входным словом, поступающим на вход автомата, начиная с момента i 1 . В связи с этим под реакцией автомата Мура, установленного в состояние a m на входное слово X=x i 1 , х i 2 , . , х ik будем понимать выходное слово той же длины у= л (a m , Х) =у i 2 , у i 3 ,., y ik +1 .
В качестве примера рассмотрим автомат Мура S5, граф которого изображен на рис.1-6, и найдем его реакцию в начальном состоянии на то же самое входное слово которое мы использовали при анализе поведения автомата Мили S1:
Как видно из этого и предыдущего примеров, реакции автоматов S5 и S1 в начальном состоянии на входное слово Х с точностью до сдвига на 1 такт совпадают (реакция автомата Мура обведена линией). Дадим теперь строгое определение эквивалентности полностью определенных автоматов.
Два автомата S A и S B с одинаковыми входными и выходными алфавитами называются эквивалентными, если после установления их в начальные состояния их реакции на любое входное слово совпадают.
Поставим в соответствие каждой паре а i /x k состояние Ь ik (i-номер состояния, k-номер входного сигнала), с учетом b 0 .
Составим таблицу переходов автомата Мура, руководствуясь следующими правилами:
1) Выпишем из таблицы 1.11 состояния автомата Мили и соответствующие каждому из них множества состояний автомата Мура (b ik ):
а 0 = {b 0 , b 02 , b 11 , b 21 }; a 1 = {b 22 }; а 2 = {b 01 , b 12 };
2) Если состояние автомата Мура b ik входит в множество, соответствующее состоянию а p автомата Мили, то в строку таблицы переходов автомата Мура для состояния b ik следует записать строку из таблицы переходов автомата Мили, соответствующую состоянию а р (из 1.10.).
3) Функцию выходов автомата Мура определим следующим образом: ? B (b ik ) =? A (а i , x k ). Для начального состояния b 0 значение выходного сигнала можно выбрать произвольно, но порождаемый начальным состоянием a 0 (с учетом понятия эквивалентности состояний). Результирующая таблица переходов и выходов автомата Мура эквивалентного автомату Мили, заданному таблицей 1.10 представлена в таблице 1.12.
4) Найдем в таблице 1.12 эквивалентные состояния и удалим их (заменим на представителя класса эквивалентности).
Если выходной сигнал возле b 0 доопределить y 1 , то окажется, что в данной таблице переходов находится 3 эквивалентных состояния (b 0 ,b 11 ,b 02 ). Заменив класс эквивалентности одним представителем (b 0 ), получим окончательную таблицу переходов (табл.1.13).
Изложенные методы взаимной трансформации автоматов Мили и Мура показывают, что при переходе от автомата Мура к автомату Мили число состояний автомата не изменяется, тогда как при обратном переходе число состояний в автомате Мура, как правило, возрастает.
Таким образом, эквивалентные между собой автоматы могут иметь различное число состояний, в связи с чем возникает задача нахождения минимального (с минимальным числом состояний) автомата в классе эквивалентных между собой автоматов. Существование для любого абстрактного автомата эквивалентного ему абстрактного автомата с минимальным числом внутренних состояний впервые было доказано Муром.
B 1 ={a 1 , a 2 , a 8 }, В 2 ={а 6 , а 9 , а 10 , а 11 , а 12 }, В 3 ={а 3 , a 4 , a 5 , a 7 }.
C 1 ={a 1 , a 2 , a 8 }, С 2 ={а 6 , а 9 , а 11 }, С 3 ={ а 10 , a 12 }, С 4 ={а 3 , а 4 , a 5 , a 7 }.
D 1 ={a 1 , a 2 , a 8 }, D 2 ={а 6 , а 9 , а 11 }, D 3 ={ а 10 , a 12 }, D 4 ={а 3 , а 4 , a 5 , a 7 }.
Разбиение ? 2 повторяет разбиение ? 1 - процедура разбиения завершена.
Выберем произвольно из каждого класса эквивалентности D 1 , D 2 , D 3 , D 4 по одному представителю - в данном случае по минимальному номеру: A'={a 1 , а 3 , a 6 , а 10 }.
Удаляя из исходной таблицы переходов "лишние" состояния, определяем минимальный автомат Мура (табл.1.15.)
1. Самофалов К.Г., Романкевич А.М., и др. Прикладная теория цифровых автоматов. - Киев. “Вища школа" 1987.
2. Соловьев Г.Н. Арифметические устройства ЭВМ. - М. “Энергия”. 1978.
3. Савельев А.Я. Прикладная теория цифровых автоматов - М. “Высшая школа”. 1987.
4. Каган Б.М. Электронные вычислительные машины и системы. - М. Энергоатомиздат. 1985.
5. Лысиков Б.Г. Арифметические и логические основы цифровых автоматов. - Минск. “Вышэйшая школа”. 1980.
Выполнение синтеза цифрового автомата Мура, осуществляющего отображение информации, приведение алфавитного отображения к автоматному. Построение формализованного описания автомата, минимизация числа внутренних состояний. Функциональная схема автомата. курсовая работа [2,8 M], добавлен 04.02.2013
Алгоритм работы автомата Мили в табличном виде. Графический способ задания автомата. Синтез автомата Мили на Т-триггерах. Кодирование состояний автомата. Таблицы кодирования входных и выходных сигналов. Таблица переходов и выходов абстрактного автомата. курсовая работа [24,7 K], добавлен 01.04.2010
Основные понятия абстрактных детерминированных автоматов Мили и Мура, как монофункциональных так и многофункциональных, реализуемых на триггерах. Понятия многофункциональных детерминированных автоматов 1-го, 2-го и 3-го рода на схемах автоматной памяти. контрольная работа [495,3 K], добавлен 28.03.2018
Изучение основных понятий теории автоматов. Анализ работы цифровых машин с программным управлением на примере автоматов Мили и Мура. Устройство преобразователей дискретной информации (RS-триггера). Разработка схемы цифрового автомата для сложения чисел. курсовая работа [449,2 K], добавлен 16.09.2017
Знакомство с табличными и графическими способами задания многофункциональных абстрактных детерминированных автоматов. Рассмотрение сфер использования абстрактных автоматов с памятью. Анализ особенностей многофункциональных автоматов Мараховского. контрольная работа [787,5 K], добавлен 28.03.2018
Синтез цифровых схем, выбор элементной базы и анализ принципов построения управляющих автоматов с жесткой логикой. Граф-схемы алгоритмов умножения и деления чисел. Создание управляющего автомата типа Мили; выбор триггера, кодирование сигналов автомата. курсовая работа [1,8 M], добавлен 18.09.2012
Теоретические основы процессоров. Построение процессоров и их общая структура. Цифровые автоматы. Расчёт количества триггеров и кодирование состояний ЦА. Структурная схема управляющего устройства. Построение графа функционирования управляющего устройства. курсовая работа [85,0 K], добавлен 08.11.2008
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Абстрактные цифровые автоматы контрольная работа. Коммуникации, связь, цифровые приборы и радиоэлектроника.
Реферат: Организация создания благоприятных условий труда на предприятии
Сочинение Музыка Бетховена
Курсовая работа по теме Тушение условного пожара в производственном корпусе деревообрабатывающего предприятия
Оценка 5 Поставлена В Дневник Ученика Сочинение
Курсовая работа по теме Периоды гражданской войны и иностранной интервенции в истории Приднестровья
Контрольная работа по теме Возрастные особенности органов дыхания
Эссе По Теме Теневая Экономика В России
Учебное Пособие На Тему Эндокринные Железы
Курсовая Работа На Тему Имидж Туристской Фирмы
Конституционные Уставные Суды Субъектов Рф Курсовая
Реферат: Причины политики либерализации в аравийских монархиях
Курсовая работа по теме Топливно-энергетический комплекс Республики Беларусь
Итоговое Сочинение 2022 Забвению Не Подлежит Произведения
Дипломная работа по теме Аналіз економічних показників діяльності підприємства ТОВ "Скандинавія"
Дипломная работа по теме Організація та шляхи вдосконалення обліку та контролю наявності та руху основних засобів
Льюис Собрание Сочинений Купить
Реферат На Тему Процессоры По Информатике
Реферат по теме Современный рынок, структура и принципы
Дипломная работа по теме Эволюция системы официальных жертвоприношений Древнего и имперского Китая
Реферат: Behavioral Learning Essay Research Paper BEHAVIORAL LEARNING
Уголовное право - Государство и право контрольная работа
Клетка и ее органоиды - Биология и естествознание презентация
Армия Пера I - История и исторические личности реферат