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

Работа 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	x 1	x 2	x 3
q 1	q 2	q 2	q 5
q 2	q 1	q 4	q 4
q 3	q 2	q 2	q 5
q 4	q 3	q 2	q 5
q 5	q 6	q 4	q 3
q 6	q 8	q 9	q 6
q 7	q 6	q 2	q 8
q 8	q 4	q 4	q 7
q 9	q 8	q 9	q 7

 

Y	x 1	x 2	x 3
q 1
q 2
q 3
q 4
q 5
q 6
q 7
q 8
q 9

Для нахождения 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	x 1	x 2	x 3
q 1	b 1	b 1	a 1
q 3	b 1	b 1	a 1
q 5	b 1	b 1	a 1
q 7	b 1	b 1	a 1
q 8	b 1	b 1	a 1
q 2	a 1	b 1	b 1
q 4	a 1	b 1	b 1
q 6	a 1	b 1	b 1
q 9	a 1	b 1	b 1

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

Для разбиения p ₃:

Для разбиения p ₄:

Для разбиения p ₅:

 

F	x 1	x 2	x 3
q 1	b 2	b 2	a 2
q 3	b 2	b 2	a 2
q 5	b 2	b 2	a 2
q 7	b 2	b 2	a 2
q 8	b 2	b 2	a 2
q 2	a 2	b 2	b 2
q 4	a 2	b 2	b 2
q 6	a 2	c 2	b 1
q 9	a 2	c 2	a 2

 

F	x 1	x 2	x 3
q 1	b 3	b 3	a 3
q 3	b 3	b 3	a 3
q 5	c 3	b 3	a 3
q 7	c 3	b 3	a 3
q 8	b 3	b 3	a 3
q 2	a 3	b 3	b 3
q 4	a 3	b 3	b 3
q 6	a 3	a 3	c 3
q 9	a 3	a 3	a 3

 

F	x 1	x 2	x 3
q 1	c 4	c 4	b 4
q 3	c 4	c 4	b 4
q 5	c 4	c 4	b 4
q 7	a 4	c 4	c 4
q 8	a 4	c 4	c 4
q 2	d 4	c 4	a 4
q 4	d 4	c 4	a 4
q 6	a 4	l 4	d 4
q 9	a 4	l 4	b 4

Так как 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м	x 1	x 2	x 3
g 1	g 2	g 2	g 3
g 2	g 1	g 2	g 2
g 4	g 4	g 2	g 1
g 4	g 1	g 5	g 4
g 5	g 1	g 5	g 3

 

Y м	x 1	x 2	x 3
q 1
q 2
q 3
q 4
q 5

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

Рис. 5.1.

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

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

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

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

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

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

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

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

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

Дата добавления: 2017-01-13