Взаимная транспозиция автоматов Мили и Мура. Освоение методов взаимного преобразования. Минимизация абстрактных автоматов

Практические задания по курсу "Теория автоматов"

Задание 1

Взаимная транспозиция автоматов Мили и Мура

Цель – практическое освоение методов взаимного преобразования автоматных моделей Мили и Мура. Проверка абстрактных автоматов Мили и Мура на эквивалентность.

Постановка задачи

Исходный абстрактный автомат задан графическим способом. При переходе от автомата Мура (A) к автомату Мили (В)

S_A = (A_A, Z_A, W_A, d_A, l_A, a_1A) → S_B = (A_B, Z_B, W_B, d_B, l_B, a_1B)

и наоборот

S_B = (A_B, Z_B, W_B, d_B, l_B, a_1B) → S_A = (A_A, Z_A, W_A, d_A, l_A, a_1A), учесть, что их входные и выходные алфавиты должны совпадать, т.е.

Z_A = Z_B ; W_A = W_B.

Подготовка к выполнению практического задания

Ознакомиться с лекционным материалом по данной тематике и соответствующими разделами в литературных источниках [1,2].

Порядок выполнения задания

  1. В соответствии с выбранным номером варианта осуществить преобразование автомата Мили в автомат Мура (Мура в Мили).

  2. Сформировать входное слово необходимой длины. Длина входного слова должна быть минимальна, но достаточна для осуществления всех имеющихся в графах автоматов переходов.

  3. Используя сформированное входное слово, осуществить проверку исходного и полученного в результате преобразования автоматов на эквивалентность. В качестве исходного состояния выбрать состояние а₁.

Варианты исходных данных

Состав отчета по заданию 1

1.  Постановка задачи.

2.  Графы исходного и преобразованного автоматов.

3.  Все этапы преобразования одной автоматной модели в другую.

4.  Входное слово минимальной длины.

5.  Реакции автоматов на входное слово.

6.  Выводы по работе.

Литература

1.  А.А.Ожиганов. Конспект лекций по курсу «Теория автоматов».

2.  С.И.Баранов. Синтез микропрограммных автоматов (граф-схемы и автоматы). Ленинград. «Энергия». Ленинградское отделение. 1979 г.

Задание 2

Минимизация абстрактных автоматов

Цель – овладение навыками минимизации полностью определенных абстрактных автоматов.

Постановка задачи

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

Подготовка к выполнению практического задания

Ознакомиться с лекционным материалом по данной тематике и соответствующими разделами в литературных источниках [1,2].

Порядок выполнения задания

  1. В соответствии с номером варианта выбрать абстрактный автомат S=(A,Z,W,δ,λ,a₁).

  2. Найти последовательные разбиения π₁, π₂,..., π_k, π_k+1 множества А на классы одно-, двух-, ... , k+1 - эквивалентных между собой состояний.

  3. Разбиение на классы производить до тех пор, пока на каком-то k+1 шаге не окажется, что π_k+1 = π_k.

  4. В каждом классе эквивалентности разбиения π выбрать по одному элементу, которые образуют множество А' состояний минимального автомата S'=(A',Z,W,δ',λ',a₁'), эквивалентного исходному автомату S.

  5. Функции переходов и выходов автомата S', определить на множестве A' *Z, то есть δ' : A' *Z → A', λ' : A' *Z → W.

  6. В качестве a₁', выбрать одно из состояний, эквивалентных a₁.

  7. Используя навыки полученные при выполнении практического задания 1, осуществить проверку исходного и минимизированного автоматов на эквивалентность.

Варианты исходных данных

          1.

2.

3.

λ	w1	w4	w1	w3	w 2	w4	w2	w2	w1	w3
δ	a1	a2	a3	a4	a 5	a6	a7	a8	a9	a10
z1	a4	a10	a4	a4	a 7	a10	a8	a7	a10	a3
z2	a7	a7	a8	a9	a 4	a8	a10	a10	a5	a8
z3	a1	a1	a1	a5	a7	a3	a5	a5	a3	a1

4.

5.

6.

λ	w1	w4	w1	w3	w2	w4	w2	w2	w1	w3
δ	a1	a2	a3	a4	a 5	a6	a7	a8	a9	a10
z1	a4	a10	a4	a1	a 7	a10	a8	a7	a10	a3
z2	a7	a7	a8	a8	a 4	a8	a10	a10	a5	a8
z3	a1	a1	a1	a3	a 7	a3	a5	a5	a3	a1

7.

Состав отчета по заданию 2

1.  Постановка задачи.

2.  Исходный абстрактный автомат.

3.  Все этапы минимизации абстрактного автомата.

4.  Минимизированный абстрактный автомат.

5.  Выводы по работе.

Литература

1.  А.А.Ожиганов. Конспект лекций по курсу «Теория автоматов».

2. С.И.Баранов. Синтез микропрограммных автоматов (граф-схемы и автоматы). Ленинград. «Энергия». Ленинградское отделение. 1979 г.

Задание 3

Канонический метод структурного синтеза

Цель – практическое освоение метода перехода от абстрактного автомата к структурному автомату.

Постановка задачи

Абстрактный автомат задан табличным способом. Причем абстрактный автомат Мили представлен таблицами переходов и выходов, а абстрактный автомат Мура - одной отмеченной таблицей переходов. Для синтеза структурного автомата использовать функционально полную систему логических элементов И, ИЛИ, НЕ и автомат Мура, обладающий полнотой переходов и полнотой выходов. Синтезированный структурный автомат представить в виде ПАМЯТИ и КОМБИНАЦИОННОЙ СХЕМЫ.

Подготовка к выполнению практического задания

Ознакомиться с лекционным материалом по данной тематике и соответствующими разделами в литературных источниках [1,2].

Порядок выполнения задания

  1.  В соответствии с номером варианта выбрать абстрактный автомат Мили или Мура.

  2.  Закодировать буквы входного алфавита, выходного алфавита и состояния абстрактного автомата двоичными кодами.

  3.  По таблицам переходов и выходов абстрактного автомата Мили (или одной