Xreferat.com » Рефераты по коммуникации и связи » Абстрактные цифровые автоматы

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

окажется, что в данной таблице переходов находится 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.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: