Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

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

Если выходной сигнал возле b₀ доопределить y₁, то окажется, что в данной таблице переходов находится 3 эквивалентных состояния (b₀,b₁₁,b₀₂). Заменив класс эквивалентности одним представителем (b₀), получим окончательную таблицу переходов (табл.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 Минимизация числа внутренних состояний автомата

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

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

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

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

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

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

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

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

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

При минимизации автомата Мура вводится понятие 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

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

₀={В₁, В₂, В₃};

B₁={a₁, a₂, a₈}, В₂={а₆, а₉, а₁₀, а₁₁, а₁₂}, В₃={а₃, a₄, a₅, a₇}.

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

У

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

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

₁={С₁, С₂, С₃, С₄};

C₁={a₁, a₂, a₈}, С₂={а₆, а₉, а₁₁}, С₃={ а₁₀, a₁₂}, С₄={а₃, а₄, a₅, a₇}.

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

У

С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

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

₁={D₁, D₂, D₃, D₄};

D₁={a₁, a₂, a₈}, D₂={а₆, а₉, а₁₁}, D₃={ а₁₀, a₁₂}, D₄={а₃, а₄, a₅, a₇}.

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

Выберем произвольно из каждого класса эквивалентности D₁, D₂, D₃, D₄ по одному представителю - в данном случае по минимальному номеру: A'={a₁, а₃, a₆, а₁₀}.

Удаляя из исходной таблицы переходов "лишние" состояния, определяем минимальный автомат Мура (табл.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.

Характеристики

Список файлов ответов (шпаргалок)