Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Контрольная работа: Абстрактные цифровые автоматы

Название: Абстрактные цифровые автоматы
Раздел: Рефераты по коммуникации и связи
Тип: контрольная работа Добавлен 09:12:42 19 января 2011 Похожие работы
Просмотров: 1053 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Содержание

1. Абстрактные цифровые автоматы

1.1 Основные понятия

1.2 Типы абстрактных автоматов

1.3 Способы задания абстрактных автоматов

1.4 Связь между моделями Мили и Мура

1.5 Эквивалентные автоматы. Эквивалентные преобразования автоматов

1.6 Минимизация числа внутренних состояний автомата

Вывод

Список литературы

Введение

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

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

1. Абстрактные цифровые автоматы

1.1 Основные понятия

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

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

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

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

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

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

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

S={ X,A,Y,,ao },

где:

X={x1 , x2 ,. xn } - множество входных сигналов (входной алфавит);

Y={y1 , y2 , ym } - множество выходных сигналов (выходной алфавит);

А={ a0 ,a1 , a2 ,. аN } - множество состояний (алфавит состояний);

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

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

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

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

ap = (ai ,Xj ).

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

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

Абстрактный автомат функционирует в дискретном автоматном времени 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)). Зависимость выходного сигнала от входного и от состояния означает, что в его составе имеется память.

1.2 Типы абстрактных автоматов

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

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)

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

у= y1 y2

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

У2 (t) = 2 (a (t));

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

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

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

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

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

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

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

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

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

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

1.3 Способы задания абстрактных автоматов

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

При табличном способе автомат задается двумя таблицами: таблицей переходов и таблицей выходов, или матрицей соединений. Таблица переходов произвольного полностью определенного автомата строится следующим образом: строки таблицы помечаютсябуквами входного алфавита автомата, а столбцы таблицы - буквами алфавита состояний автомата; В клетке таблицы переходов, находящейся напересечении строки, отмеченной входным сигналом xi , и столбца отмеченного состоянием aj , ставится состояние аk , являющееся результатом перехода автомата из состояния aj под воздействием входного сигнала хi , что определяется выражением ak = (aj , хj ).

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

Состояния

а1

а2

аk

входные сигналы
x1 (a1 ,x1 ) (a2 , x1 ) . к , x1 )
хj (a1 , хj ) (a2 , хj )

к , хj )

Пример заполнения таблицы переходов некоторого абстрактного полностью определенного автомата с входным алфавитом X={х1 , х2 } - и алфавитом состояний A={a1 , a2 , а3 } представлен в табл.1.2.

Таблица 1.2

А

а1

a2

а3

х

х1

а2

а3

а1

x2

а1

а1

a2

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

Заполнение остальных клеток аналогично случаю полностью определенного автомата. Вид таблицы переходов не зависит от типа задаваемого автомата (автомат Мили, Мура, С-автомат). Таблицы выходов автоматов Мили, Мура, С-автомата имеют различия.

Таблица выходов полностью определенного автомата Мили строится следующим образом: идентификация столбцов и строк, а также формат таблицы соответствуют таблице переходов полностью определенного автомата. В клетке таблицы выходов, находящейся на пересечении строки, отмеченной входным сигналом Xj , и столбца, отмеченного состоянием ак , ставится выходной сигнал Уm , который автомат выдает, находясь в состоянии аk при наличии входного сигнала Xj, что определяется выражением Ym=k , хj ).


Таблица 1.3 Таблица выходов абстрактного автомата Мили.

Состояния

a1

a2

ak

Входные сигналы

х1

(a1 ,x1 )

(a2 , x1 )

(ak , x1 )

….

.

хj

(a1 ,xj ) (a2 , xj ) (aк , xj )

Пример заполнения таблицы выходов некоторого абстрактного полностью определенного автомата с входным алфавитом X={x1 , x2 }, алфавитом состояний A={a1 , а2 , а3 } и выходным алфавитом Y={y1 , y2 , y3 }-представлен в табл.1.4.

Таблица 1.4

a a1

a2

a3

x
x1 у2 у3 y1
x2 y3 у1 у2

Таблица выходов полностью определенного автомата Мура строится более просто: каждому состоянию автомата ставится в соответствие свой выходной сигнал. Пример таблицы выходов автомата Мура с алфавитом состояний A={a1 , а2 , а3 } и выходным алфавитом Y={y1 , y2 , у3 } представлен в таблице 1.5.

Таблица 1.5

А a1 a2 a3
у y1 y2 y2

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

На практике таблицы переходов и выходов часто совмещают в одну таблицу, называемую отмеченной таблицей переходов автомата. Примеры отмеченных таблиц переходов представлены в табл.1.6. - 1.8 (Общий вид отмеченной таблицы переходов - табл.1.6., отмеченная таблица переходов автомата Мили - табл.1.7., отмеченная таблица переходов автомата Мура - табл.1.8.).

Кроме рассмотренных выше таблиц переходов и выходов произвольный абстрактный автомат может быть задан матрицей соединений.

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

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

Таблица 1.6

Состояния

a1

a2

ak

Входные сигналы
x1  (a1 ,x1 ))  (a2 ,x1 )  (ak ,x1 )
 (a1 ,x1)  (a2 ,x1 )  (ak ,x1 )

xj

 (a1 ,xj )  (a2 , xj )  (аk , xj )
 (a1 ,xj )  (a2 , xj )  (аk , xj )

Таблица 1.7

A

X

a1

a2

a3

x1

a2 /y2 a3 /y3 a13

x2

a13 a1 /y1 a2 /y2

Таблица 1.8

Y

y1

y2

y3

A

X

a1

a2

a3

x1

a2

a3

a1

x2

a1

a1

a2

Таблица 1.9.

a1 an
a1 xj (yk )
an x| (ym )

При графическом способе задания абстрактные автоматы представляются ориентированными графами. Графом автомата называется ориентированный связный граф, вершины которого соответствуют состояниям автомата, а дуги между ними - переходам между состояниями. Две вершины ak и as соединяются дугой в том случае, если в автомате имеется переход из состояния ak в состояние as . Для автомата Мили входной и выходной сигналы проставляются на дуге, соответствующей данному переходу (рис 1.3.), для автомата Мура входной сигнал проставляется на дуге, а выходной - рядом с вершиной, соответствующей состоянию (рис 1.4.).

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

Рисунок 1.3-Граф автомата Мили Рисунок 1.4-Граф автомата Мура

При аналитическом способе задания абстрактные автоматы задаются четверкой объектов:

S={ X,A,Y,F}, где Fзадает для каждого состояния аj автомата отображение (ХхА) - > (AxY). Другими словами, при аналитическом способе задания для каждого состояния автомата аj указывается отображение Fai , представляющее собой множество всех троек ар , xm , yk , и таких, что под воздействием входного сигнала xm автомат переходит из состояния а j в состояние ар , выдавая при этом выходной сигнал yk .

Применительно к общему определению абстрактного автомата, последнее равнозначно описанию функций δи λв соответствии с выражением: ap = δ (ai , xm ), yк = λ (ai , xm ).

Отображение Fai записывается следующим образом:

Fai {ap (Xm /yk ),ai (Xf /yz ) …}.

Для абстрактного автомата Мили (табл.1.7.) аналитическое задание имеет следующий вид:

S={ X,A,Y,F}, X={x1 ,x2 }, A={a1 , а2 , а3 }, Y={y1 , y2 , у3 },

Fa1 ={a2 (x1 /y2 ), a1 (x23 ) },

Fа 2 ={а3 (x1 /y3 ), a1 (x2 /y1 ) },

Fa 3 ={a1 (x1 /y3 ), а2 (x2 /y2 ) }.

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

Определим синхронные и асинхронные автоматы. Состояние аs автомата Sназывается устойчивым cостоянием, если для любого входного сигнала хj Х, такого, что аs = δ (аi Хm ) имеет место as = δ (as , xm ).

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

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

1.4 Связь между моделями Мили и Мура

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

Пусть абстрактный автомат Мили задан графом рис.1.5.

На вход этого автомата, установленного в начальное состояние, поступает входное слово X=x1 , x1 , x2 , x1 , x2 , x2 .

Рисунок 1.5 - Граф автомата Мили

Так как  (a1 , x1 ) = а3 , a (a1 , x1 ) = y1 , то под действием первой буквы слова Х входного сигнала x1 автомат перейдет в состояние a3 и на выходе его появится сигнал y1. Далее,  (а3 , x1 ) = a1 , а  (а3 , x1 ) = у2 , потому при приходе второго сигнала x1 автомат окажется в состоянии a1 , а на выходе его появится сигнал у2 . Проследив непосредственно по графу или таблицам переходов и выходов дальнейшее поведение автомата, опишем его тремя строчками, первая из которых соответствует входному слову X, вторая - последовательности состояний, которые проходит автомат под действием букв слова X, третья - выходному слову У, которое появляется на выходе автомата:

x1 x1 x2 x1 x2 x2

a1 а3 a1 a1 а3 a2 а3

y1 y2 y1 y1 y1 y2

Назовем у =  (а1 , X) реакцией автомата Мили в состоянии a1 на входное слово X. Как видно из примера, в ответ на входное слово длины kавтомат Мили выдает последовательность состояний длины к+1 и выходное слово длины k. В общем виде поведение автомата Мили, установленного в состояние аm , можно описать следующим образом:

Входное слово xi 1 xi 2 xi 3
Последовательность состояний am ai2 = (am ,xi1 ) ai3 = (ai2 ,xi2 ).
Выходное слово yi 1 = (am ,xi 1 ) yi2 = (ai2 ,xi2 ) yi3 = (ai3 ,xi3 )

Точно так же можно описать поведение автомата Мура, находящегося в состоянии am , при приходе входного слова xi 1 , xi2 ,., хik . Напомним, что в соответствии с (1-2) выходной сигнал в автомате Мура в момент времени t (У (t)) зависит лишь от состояния, в котором находится автомат в момент t (a (t)):

Входное слово xi 1 xi 2 xi 3
Последовательность состояний am ai2 = (am ,xi1 ) ai3 = (ai2 ,xi2 ) ai4 = (ai3 ,xi3 )
Выходное слово yi 1 = (am ,xi 1 ) yi2 = (ai2 ,xi2 ) yi3 = (ai3 ,xi3 ) yi 4 = (ai 4 )

Очевидно, что выходной сигнал уi1 =λ (am ) в момент времени i1 не зависит от входного сигнала xi 1 , а определяется только состоянием аm .

Таким образом, этот сигнал yi 1 никак не связан с входным словом, поступающим на вход автомата, начиная с момента i1 . В связи с этим под реакцией автомата Мура, установленного в состояние am на входное слово X=xi 1 , хi2 ,., хik будем понимать выходное слово той же длины у= λ (am ,Х) =уi2 , уi3 ,., yik +1 .

В качестве примера рассмотрим автомат Мура S5, граф которого изображен на рис.1-6, и найдем его реакцию в начальном состоянии на то же самое входное слово которое мы использовали при анализе поведения автомата Мили S1:

Входное слово x1 x1 x2 x1 x2 х2
Последовательность состояний a1 a4 a1 a1 a4 a3 a5
Выходное слово y1 y1 y2 y1 y1 y1 y2

Рисунок 1-6 - Граф автомата Мура

Как видно из этого и предыдущего примеров, реакции автоматов S5 и S1 в начальном состоянии на входное слово Х с точностью до сдвига на 1 такт совпадают (реакция автомата Мура обведена линией). Дадим теперь строгое определение эквивалентности полностью определенных автоматов.

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

1.5 Эквивалентные автоматы. Эквивалентные преобразования автоматов

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

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

Рассмотрим сначала преобразование автомата Мура в автомат Мили.

Пусть дан автомат Мура: SA ={ ХA , АA , УA ,A ,A , ао A }, где:

ХA ={х1 , х2 ,. хn }; Y={y1 , у2 ,. уm }; А={ а0 , а1 , а2 ,. аN }; а0 A = а0 - начальное состояние (а0 A А); A - функция переходов автомата, задающая отображение (ХA хАA ) - >АA ; A - функция выходов автомата, задающая отображение АA ->УA .

Построим автомат Мили: SB ={ ХB , АB , YB ,B , B , а0 B }, у которого АBA ; ХBA ; YBA ; B =A ; а0 B0 A. Функцию выходов B определим следующим образом. Если в автомате Мура Am , х1 ) = аs и As ) =yg , то в автомате Мили B (am , х1 ) =yg

Рисунок 1.7 - Иллюстрация перехода от модели Мура к модели Мили

Переход от автомата Мура к автомату Мили при графическом способе задания иллюстрируется рис.1-7: выходной сигнал yg записанный рядом с вершиной (as ), переносится на все дуги, входящие в эту вершину.

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

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

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

SA ={ ХA , АA ,YA , A , A , a0 A },

где:

ХA ={x1 , x2 ,. xn }; Y={y1 , у2 ,. ym }; А={ a0 ,a1 ,a2 ,. aN }; a0 A = a0 - начальное состояние (а0 A А); A - функция переходов автомата, задающая отображение (ХAA ) - >АA ; A - функция выходов автомата, задающая отображение (ХAA ) - >YA .

Построим автомат Мура: SB ={XB , AB , YB , B , B , a0 B }, у которого XB =XA ; YB =YA .

Для определения AB каждому состоянию as АA поставим в соответствие множество As всевозможных пар вида (as , yg )

Функцию выходов B определим следующим образом. Каждому состоянию автомата Мура SB , представляющему собой пару вида (as ,yg ), поставим в соответствие выходной сигнал yg .

Если в автомате Мили SA был переход A (am , xf ) = as и при этом выдавался выходной сигнал A (am ,xf ) =yg , то в SB будет переход из множества состояний Am , порождаемых am , в состояние (as ,yg ) под действием входного сигнала xf .

В качестве начального состояния a0 B можно взять любое из состояний множества A0 , которое порождается начальным состоянием a0 автомата SA . При этом выходной сигнал в момент времени t=0 не должен учитываться.

Рассмотрим пример. Пусть задан автомат Мили (табл.1.10.)

Таблица 10 Таблица 11
A

x1

x2

X

А

x1 x2

a0

a2 /y1

a01

a0

b0

a2 /y1

b01

a0 /y1

b02

a1

a0 /y1

а2 /y2

a1

a0 /y1 b11

а2 /y2

b12

a3 a0 /y2

a1 /y1

a2

a0 /y2

b21

a1 /y1

b22

Поставим в соответствие каждой паре аi /xk состояние Ьik (i-номер состояния, k-номер входного сигнала), с учетом b0 .

Составим таблицу переходов автомата Мура, руководствуясь следующими правилами:

1) Выпишем из таблицы 1.11 состояния автомата Мили и соответствующие каждому из них множества состояний автомата Мура (bik ):

а0 = {b0 , b02 , b11 , b21 }; a1 = {b22 }; а2 = {b01 , b12 };

2) Если состояние автомата Мура bik входит в множество, соответствующее состоянию аp автомата Мили, то в строку таблицы переходов автомата Мура для состояния bik следует записать строку из таблицы переходов автомата Мили, соответствующую состоянию ар (из 1.10.).

3) Функцию выходов автомата Мура определим следующим образом: B (bik ) =Ai , xk ). Для начального состояния b0 значение выходного сигнала можно выбрать произвольно, но порождаемый начальным состоянием a0 (с учетом понятия эквивалентности состояний). Результирующая таблица переходов и выходов автомата Мура эквивалентного автомату Мили, заданному таблицей 1.10 представлена в таблице 1.12.

4) Найдем в таблице 1.12 эквивалентные состояния и удалим их (заменим на представителя класса эквивалентности).

Если выходной сигнал возле b0 доопределить y1 , то окажется, что в данной таблице переходов находится 3 эквивалентных состояния (b0 ,b11 ,b02 ). Заменив класс эквивалентности одним представителем (b0 ), получим окончательную таблицу переходов (табл.1.13).

Таблица 1.12

x1 x2 Y
b0 b01 b02 y1
b01 b21 b22 y1
b02 b01 b02 y1
b11 b01 b02 y1
b12 b21 b22 y2
b21 b01 b02 y2
b22 b11 b12 y1

Таблица 1.13.

x1 x2 У
b0 b01 b0 y1
b01 b21 b22 y1
b12 b21 b22 y2
b21 b01 b0 y2
b22 b0 b12 y1

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

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

1.6 Минимизация числа внутренних состояний автомата

Алгоритм Ауфенкампа-Хона.

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

Два состояния автомата am и as называются эквивалентными (am =as ), если  (am ,X) =  (as ,X) для всех возможных входных слов длины X.

Если am и as не эквивалентны, они различимы. Более слабой эквивалентностью является K-эквивалентность. Состояния am и аs K-эквивалентны, если  (am , Хk ) =  (as , Хk ) для всех возможных входных слов длины К. При минимизации числа внутренних состояний автомата Мили S={X,Y, А, , , а0 } используется алгоритм Ауфенкампа-Хона:

1. Находят последовательные разбиения 1 ,2 ,…,k ,k +1 , множества А на классы одно-, двух-,., К-, (К+1) - эквивалентных состояний до тех пор, пока на каком-то (К+1) шаге не окажется, что k =k +1 . В этом случае К-эквивалентные состояния являются эквивалентными. Число шагов К, при котором k =k +1 не превышает N-1, где N - число внутренних состояний автомата.

2. В каждом классе эквивалентности выбирают по одному элементу (представителю класса), которые образуют множества А' состояний минимального автомата S'.

3. Функцию переходов ' и выходов ' автомата S' определяют на множестве A'xX.

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

4. В качестве а'0 выбирается одно из состояний, эквивалентное состоянию а0 . В частности, удобно принять само состояние а0 .

При минимизации автомата Мура вводится понятие 0-эквивалентности состояний и разбиения множества состояний на 0-классы: 0-эквивалентными называются любые, одинаково отмеченные выходными сигналами, состояния автомата Мура. В качестве примера рассмотрим минимизацию автомата Мура, заданного таблицей переходов и выходов (Таблица 1.14).

Таблица 1.14

У y1 y1 y3 y3 y3 y2 y3 y1 y2 y2 y2 y2
А a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12
x2 a10 a12 a5 a7 a3 a7 a3 a10 a7 a1 a5 a2
x2 a5 a7 a6 a11 a9 a11 a6 a4 a6 a8 a9 a8

Выполним разбиение 0 :

0 ={В1 , В2 , В3 };

B1 ={a1 , a2 , a8 }, В2 ={а6 , а9 , а10 , а11 , а12 }, В3 ={а3 , a4 , a5 , a7 }.

Построим таблицу разбиения 0 :

У B1 В2 В3
А a1 a2 a8 a6 a9 a10 a11 a12 a3 а4 a5 a7
х1 В2 В2 В2 В3 В3 B1 В3 B1 В3 В3 В3 , В3
х2 В3 В3 В3 В2 В2 B1 B2 B1 В2 В2 В2 В2

Выполним разбиение 1 :

1 ={С1 , С2 , С3 , С4 };

C1 ={a1 , a2 , a8 }, С2 ={а6 , а9 , а11 }, С3 ={ а10 , a12 }, С4 ={а3 , а4 , a5 , a7 }.

Построим таблицу разбиения 1 :

У С1 С2 С3 С4
А a1 a3 a8 a6 a9 a11 a10 a12 a3 а4 a5 a7
х1 С3 С3 С3 С4 С4 С4 C1 C1 С4 C4 С4 С4
х2 С4 С4 С4 С2 С2 С2 C1 C1 С2 С2 С2 С2

Выполним разбиение 2 .

1 ={D1 , D2 , D3 , D4 };

D1 ={a1 , a2 , a8 }, D2 ={а6 , а9 , а11 }, D3 ={ а10 , a12 }, D4 ={а3 , а4 , a5 , a7 }.

Разбиение 2 повторяет разбиение 1 - процедура разбиения завершена.

Выберем произвольно из каждого класса эквивалентности D1 , D2 , D3 , D4 по одному представителю - в данном случае по минимальному номеру: A'={a1 , а3 , a6 , а10 }.

Удаляя из исходной таблицы переходов "лишние" состояния, определяем минимальный автомат Мура (табл.1.15.)

Таблица 1.15.

У y1 y3 y2 y2
А a1 a3 a6 a10
х1 a10 a3 a3 a1
х2 a3 a6 a6 a1

Вывод

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

Список литературы

1. Самофалов К.Г., Романкевич А.М., и др. Прикладная теория цифровых автоматов. - Киев. “Вища школа" 1987.

2. Соловьев Г.Н. Арифметические устройства ЭВМ. - М. “Энергия”. 1978.

3. Савельев А.Я. Прикладная теория цифровых автоматов - М. “Высшая школа”. 1987.

4. Каган Б.М. Электронные вычислительные машины и системы. - М. Энергоатомиздат. 1985.

5. Лысиков Б.Г. Арифметические и логические основы цифровых автоматов. - Минск. “Вышэйшая школа”. 1980.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений08:02:47 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
09:23:55 29 ноября 2015

Работы, похожие на Контрольная работа: Абстрактные цифровые автоматы
Нейрокомпьютерные системы
Введение. ПОЧЕМУ ИМЕННО ИСКУССТВЕННЫЕ НЕЙРОННЫЕ СЕТИ? После двух десятилетий почти полного забвения интерес к искусственным нейронным сетям быстро ...
Входные сигналы сразу же порождают выходной сигнал.
Каждый слой в результате этого имеет более абстрактную, менее специфичную реакцию по сравнению с предшествующим; выходной слой реагирует на полные образы, показывая высокую степень ...
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 1763 Комментариев: 4 Похожие работы
Оценило: 4 человек Средний балл: 4.8 Оценка: неизвестно     Скачать
Технология извлечения знаний из нейронных сетей: апробация ...
Министерство образования Российской Федерации Омский Государственный Университет Математический факультет Горбань Павел Александрович ТЕХНОЛОГИЯ ...
Можно представить вычисление F(x) как результат работы n автоматов, каждый из которых имеет один вход и выдает на выходе значение fi (A), где A - входной сигнал (рис.8, а). Чтобы ...
Пусть Y - выходной сигнал нейрона, Yi - i-е дискретное значение выхода (в случае дискретнозначного выхода), X1,..,Xn - входные сигналы нейрона, xij - j-e дискретное значение i-го ...
Раздел: Рефераты по информатике, программированию
Тип: дипломная работа Просмотров: 413 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Структурные автоматы
СОДЕРЖАНИЕ Введение 1. Основные понятия. Канонический метод структурного синтеза автоматов. Теорема Глушкова о структурной полноте 2. Основные этапы ...
Если абстрактный автомат был лишь математической моделью дискретной системы, то в структурном автомате учитывается структура входных и выходных сигналов автомата, а также его ...
Например, X={x1, x2, x3, x4, x5} - входной алфавит абстрактного автомата.
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Просмотров: 2354 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Цифровая обработка сигналов
ВВЕДЕНИЕ В ЦИФРОВУЮ ОБРАБОТКУ СИГНАЛОВ Содержание. 1. Дискретные сигналы 1.1. Дискретизация непрерывных сигналов 1.2. Связь спектров дискретных и ...
Отсюда, по теореме о свертке, свертка входного сигнала с импульсной характеристикой дает сигнал на выходе цепи
H(Z) = a2 + a1Z-1 + a0Z-2 + a1Z-3 + a2Z-4 = Z-2 [a0 + a1 (Z + Z-1) + a2 (Z2 + Z-2)]
Раздел: Рефераты по радиоэлектронике
Тип: реферат Просмотров: 3149 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Устройство управления синхронного цифрового автомата
Введение. Характерная черта научно-технического прогресса, определяющего дальнейший мощный подъём общественно-технического производства: широкое ...
Различие между ними заключается в том, что в абстрактной теории мы отвлекаемся от структуры, как самого автомата, так и его входных и выходных сигналов.
Так, видно, что состояние выходного сигнала Y10 соответствует состоянию входных сигналов X1, X4 и X6.
Раздел: Остальные рефераты
Тип: реферат Просмотров: 1583 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Синтез цифрового автомата
Министерство образования Российской Федерации Архангельский государственный технический университет Факультет промышленной энергетики, IV курс 3 ...
Цифровым автоматом называют дискретный преобразователь информации, способный принимать различные состояния, переходить под воздействием входных сигналов, или команд программы ...
На вход автомата подаются входные сигналы x1.x5, на выходе формируются сигналы для управления некоторым устройством y1.y7.
Раздел: Рефераты по коммуникации и связи
Тип: курсовая работа Просмотров: 1535 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Коммутация в сетях с использованием асинхронного метода переноса и ...
ВВЕДЕНИЕ В 1998 году специалисты компании Lucent Tehnologies обратили внимание на то, что в США за последние 15 лет скорость работы запоминающих ...
Вывод am узла X=(a1, a2...an-1) соединен со вводом а1 узла Y=(a2, а3......аn) следующего каскада.
- Монотонность Y1<Y2 <....<Yk или Y1>Y2>...>Yk
Раздел: Рефераты по коммуникации и связи
Тип: дипломная работа Просмотров: 1296 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Все работы, похожие на Контрольная работа: Абстрактные цифровые автоматы (2672)

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(151206)
Комментарии (1843)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru