Работа 5. минимизация на эвм конечных автоматов с памятью

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

Задание

1. Для заданного преподавателем в виде графа КА (КА1) составить таблицы переходов и выходов. Подготовить предложения для представления на ЭВМ КА1.

2. Найти для КА1 К - эквивалентные состояния. (К=1, 2).

3. Для КА1 найти p - разбиение и построить минимальный КА1 (МКА 1).

4. Получить на ЭВМ минимальный КА1 и сравнить результаты с п.3.

Общие сведения

Представляется очевидным, что одно и то же автоматное преобразование может быть реализовано разными конечными автоматами, различающимися множествами внутренних состояний Q и, как следствие, функциями переходов F и выходов Y [1, 7, 8]. Поэтому для каждого автоматного преобразования должна существовать форма, его реализующая и обладающая наименьшим числом внутренних состояний. Назовем такой конечный автомат минимальным, а процесс его определения – минимизацией конечных автоматов с памятью.

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

Методические указания

1. Формализованное представлениеКА. При формализованном представлении КА необходимо составить таблицу переходов и выходов для синхронного и асинхронного КА1, а также составить совмещенные таблицы.

Для представления на ЭВМ КА необходимо определить, какие переменные КА и массивы будут использованы. Эти данные необходимо согласовать с преподавателем.

2. Определение К- эквивалентных состояний и p-разбиение рассмотрим на примере построения минимального КА, заданного в виде:

X = {x₁, x₂, x₃}, Y = {0, 1}, Q = {q₁, q₂, q₃, q₄, q₅, q₆, q₇, q₈, q₉},

где X - множество входных состояний; Y - множество выходных состоянии; Q - множество внутренних состояний КА; F - таблица переходов; Y - таблица выходов. Таблицы переходов и выходов заданы следующие:

Таблица переходов	Таблица выходов
F x1 x2 x3 q1 q2 q2 q5 q2 q1 q4 q4 q3 q2 q2 q5 q4 q3 q2 q5 q5 q6 q4 q3 q6 q8 q9 q6 q7 q6 q2 q8 q8 q4 q4 q7 q9 q8 q9 q7	Y x1 x2 x3 q1 q2 q3 q4 q5 q6 q7 q8 q9

Для нахождения p - разбиения определим последовательно p₁, p₂ и т. д. разбиения. Для КА1 на основании таблицы выходов p₁ - разбиение состоит из двух классов:

a₁ = {q₁, q₃, q₅, q₇, q₈}; b₁ = {q₂, q₄, q₆, q₉}.

В дальнейшем индексами a_k, b_k, c_k, d_k и т.д. будем обозначать множества, состоящие из эквивалентных состояний КА в p_k - разбиении.

Для построения p₂ - разбиения составим таблицу переходов:

F	x1	x2	x3
q1	b1	b1	a1
q3	b1	b1	a1
q5	b1	b1	a1
q7	b1	b1	a1
q8	b1	b1	a1
q2	a1	b1	b1
q4	a1	b1	b1
q6	a1	b1	b1
q9	a1	b1	b1

При p₂ - разбиении имеем три класса эквивалентных состояний a₂, b₂, c₂. Аналогично определяются разбиения p₃, p₄, p₅.

Для разбиения p3:	Для разбиения p4:	Для разбиения p5:
F x1 x2 x3 q1 b2 b2 a2 q3 b2 b2 a2 q5 b2 b2 a2 q7 b2 b2 a2 q8 b2 b2 a2 q2 a2 b2 b2 q4 a2 b2 b2 q6 a2 c2 b1 q9 a2 c2 a2	F x1 x2 x3 q1 b3 b3 a3 q3 b3 b3 a3 q5 c3 b3 a3 q7 c3 b3 a3 q8 b3 b3 a3 q2 a3 b3 b3 q4 a3 b3 b3 q6 a3 a3 c3 q9 a3 a3 a3	F x1 x2 x3 q1 c4 c4 b4 q3 c4 c4 b4 q5 c4 c4 b4 q7 a4 c4 c4 q8 a4 c4 c4 q2 d4 c4 a4 q4 d4 c4 a4 q6 a4 l4 d4 q9 a4 l4 b4

Так как p₄ эквивалентно p₅, то разбиения прекращаем и полученное разбиение p = p₄ является предельным.

3. Для построения минимального КА каждому множеству эквивалентныx состояний a₄, b₄, c₄d₄l₄ в p - разбиении поставим в соответствие одно внутреннее состояние g₁, g₂, g₃, g₄, g₅ минимального конечного автомата

A_M (X, G_M, Y, F_M, Y_M),

где G_M = (g₁, g₂, g₃, g₄, g₅).

F_M определяется следующим образом:

Если F (q_j, x)ÎG_S, q_jÎG_l, то F _M(g_l, x) = q_S.

Например: F (q₁, x₁)ÎG₂, q₁ÎG₁, следовательно, F _M(g₁, x₁) = g₂.

Y_Mопределяется следующим образом:

Если Y (q_j, x) = Y_k, q_jÎG_S, то Y_M(g_S, x) = Y_k.

Например: Y (q₁, x₁) = 1, q₁ÎG₁, следовательно, Y_M(g₁, x₁) = 1.

В результате получим минимальный КА, для которого G_M = (g₁, g₂, g₃, g₄, g₅) и таблицы переходов и выходов имеют вид:

Таблица переходов	Таблица выходов
Fм x1 x2 x3 g1 g2 g2 g3 g2 g1 g2 g2 g4 g4 g2 g1 g4 g1 g5 g4 g5 g1 g5 g3	Y м x1 x2 x3 q1 q2 q3 q4 q5

Граф данного КА приведен на рис. 5.1.

Рис. 5.1.

Контрольные вопросы

1. Каковы свойства p_k - разбиения?

2. Чем определяется эквивалентность состояний КА?

3. Чему равно k в p_k - разбиении, если число внутренних состояний исходного и минимального КА совпадает?

4. Чему равно максимальное число внутренних состояний в минимальной КА?

5. Могут ли два КА быть эквивалентными, если число их внутренних состояний различно?

6. Какие формы заданий КА наиболее удобны для представления его на ЭВМ?

Задание для курсовой работы

Цель курсовой работы: освоение методики аналитического исследования конечного автомата без памяти с двоичными входами и выходами с помощью функций алгебры логики (ФАЛ, реализация полученного конечного автомата в форме логической сети (часть 1); освоение математического аппарата задания, анализа графовых моделей дискретных систем и решения ряда основных задач на графах (часть 2).

Часть 1

Система подвержена действию 3-х видов двоичных входных сигналов (факторов) x₁, x₂, x₃. Реакция системы определяется двоичными выходными сигналами y₁, y₂, y₃. Соответствие между входными (i) и выходными (j) двоичными наборами задается таблицей, где i, j - десятичные номера наборов.

i
j

Требуется:

1. Дать формальное описание данной системы, как конечного автомата без памяти, составить таблицы истинности описывающих ФАЛ y_k= f_k(x₁,x₂,x₃), к = 1,2,3.

2. Исследовать каждую из ФАЛ f₁, f₂, f₃,на наличие фиктивных аргументов, при обнаружении таковых осуществить соответствующие упрощения.

3. Записать СДНФ, СКНФ, полином Жегалкина ФАЛ f₁, f₂, f₃, на основе использования карт Вейча, найти их МДНФ и МКНФ, а затем наилучшие скобочные формы, сравнить их по сложности (числу букв).

4. Установить принадлежность f₁, f₂, f₃ предполным классам: Р₀, P₁, L, М, S.

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

6. Записать перестановочную (инцидентную) матрицу данного конечного автомата.

7. Определить - зависимы ли f₁, f₂, f₃, при положительном ответе выразить зависимость в аналитической форме.

8. Установить, существует ли система ФАЛ: Z₁=f₁ (y₁, y₂, y₃,); Z₂=f₂ (y₁, y₂, y₃,), позволяющая различать следующие наборы входных факторов x₁,x₂,x₃: <000>, <010>, <101>, <111>. В случае положительного ответа получить одно из решений, совместив доопределение ФАЛ и их минимизацию в классе ДНФ.

Часть 2

ДАНО: Два графа G (X, F) и H (Y, P).

НЕОБХОДИМО:

1. Построить аналитически и графически объединение, пересечения, разность графов G и H, дополнение графа G по отображению до универсального.

2. Для графа S = G U H построить матрицы смежности, инцидентности, достижимости; конденсацию и базу графа; минимальные и наименьшее доминирующие множества.

3. Для графа S = G U H построить Гамильтонов и Эйлеров путь (если они не существуют, то дополнить граф необходимыми дугами, обозначив их на графе). Гамильтонов путь построить с использованием алгоритма Робертса и Флореса [6].

Варианты заданий для курсовой работы приведены в Приложении.

ЛИТЕРАТУРА

1. Босин П.Л., Булыгии В.С., Кулешов К.Г. Лабораторные работы но курсу «Основы теории конечных динамических систем», — М.: МАИ, 1985.

2. Булыгин B.C. Логические основы теории дискретных устройств: учеб. пособие. - M.: МАИ, 1983.

3. Булыгин B.C. Основы проектирования дискретных устройств АСУ: учеб. пособие. - M.: МАИ, 1982.

4. Поспелов Д.А. Логические методы анализа и синтеза схем. - М.: Энергия, 1968.

5. Просветов Г.И. Дискретная математика:задачи и решения: учебное пособие. – М.:БИНОМ. Лаборатория знаний,2008. – 222 с.

6. Кристофидес Н, Теория графов: Алгоритмический подход. - М.: Мир, 1978.

7. Булыгин B.C., Ескин В.И.. Модели дискретных устройств с памятью в АСУ: Учеб. пособие. - M.: Изд-во МАИ, 1993. - 72 с.: ил.

8. Мелихов A.H. Ориентированные графы и конечные автоматы. - M.: Наука, 1971.

ПРИЛОЖЕНИЕ

Варианты заданий для поиска гамильтонова пути в графе

Вариант 1. Вариант 2.

Вариант 3. Вариант 4.

Вариант 5. Вариант 6.

Вариант 7. Вариант 8.

Вариант 9. Вариант 10.

Варианты заданий для поиска эйлерового пути в графе

Вариант 1. Вариант 2.

Вариант 3. Вариант 4.

Вариант 5. Вариант 6.

Вариант 7. Вариант 8.

Вариант 9. Вариант 10.

Варианты заданий для поиска компонент связности в графе

Вариант 1 Вариант 2

Вариант 3 Вариант 4

Вариант 5 Вариант 6

Вариант 7 Вариант 8

Вариант 9 Вариант 10

Варианты заданий для курсовой работы

(Часть 1)

	i	0 1 2 3 4 5 6 7
j		1 0