Тема 7. Минимальная форма автомата.

Пусть А – автомат с m классами эквивалентности: P_экв = {Σ ₁, Σ ₂, …, Σ _m}, m ≤ n, n = |S|. Введем обозначение s⁽ⁱ⁾ для любого состояния, входящего в класс Σ _i:

Минимальной формой автомата А называют автомат Ã, имеющий m состояний, которые образуют множество:

{s⁽¹⁾, s⁽²⁾, …, s^(m)}.

Процесс отыскания минимальной формы называют минимизацией автомата. Полученный автомат называют минимальным. Очевидно, минимизация состоит в определении P_экв и последующем построении характеристических функций автомата Ã с учетом того, что каждый класс в P_экв – это одно состояние Ã.

Таким образом, индивидуальное распознавание каждого состояния исходного автомата становится ненужным: важно только определить, к какому классу эквивалентности оно относится.

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

Алгоритм двухэтапный, заключается в поиске пар эквивалентных состояний.

Этап 1, шаг 1. Получение первичного разбиения.

Два состояния s_i и s_j относим к одному классу эквивалентности Σ _1h, если для каждого x_k Î X выполняется равенство: f_y(s_i, x_k) = f_y(s_j, x_k), т.е. при любом входном воздействии реакция автомата одинакова в обоих состояниях.

Этап 2, шаг (i + 1), i ≥ 1. Итерационное разбиение ранее полученных классов.

Два состояния s_u и s_v, принадлежащие одному классу эквивалентности Σ _ij (индекс i – нумерация шага, индекс j – нумерация класса), относим к классу Σ _i+1j, если для каждого x_k Î X верно:

т.е. под воздействием каждого входного сигнала автомат, находясь как в s_u, так и в s_v, переходит в состояния, принадлежащие одному и тому же классу эквивалентности Σ _iw предыдущего разбиения.

Алгоритм завершается при совпадении разбиений на очередном и предыдущем шагах.

Пример. Автомат Мили А задан таблицей переходов/выходов (рис. 7.1). Состояния для краткости обозначены цифрами 1, 2, …, 9. Выполнить минимизацию автомата алгоритмом Мили.

y(t)	s(t+1)
x(t) s(t)	a1	a2	a3	a1	a2	a3

Рис. 7.1. Таблица переходов/выходов исходного автомата A.

Шаг 1.

В результате первичного разбиения имеем три класса эквивалентности:

Σ ₁₁ = {1, 4, 6, 9}, Σ ₁₂ = {2, 3, 8}, Σ ₁₃ = {5, 7}.

Шаг 2.

x(t) s(t)

s(t+1)

x(t) s(t)

s(t+1)

x(t) s(t)

s(t+1)

a1

a2

a3

a1

a2

a3

a1

a2

a3

Σ 11

Σ 12

Σ 11

Σ 11

Σ 12

Σ 11

Σ 11

Σ 13

Σ 13

Σ 11

Σ 11

Σ 12

Σ 12

Σ 11

Σ 11

Σ 11

Σ 11

Σ 13

Σ 11

Σ 11

Σ 12

Σ 12

Σ 11

Σ 11

Σ 11

Σ 11

Σ 13

Σ 13

Σ 11

Σ 13

Пояснение. Последовательно рассматриваем классы, полученные на предыдущем шаге. В текущем классе для каждого состояния и каждого входного сигнала определяем, какому классу предыдущего шага принадлежит состояние, в которое переходит автомат в момент времени t+1.

На шаге 2 получаем разбиение:

Σ ₂₁ = {1, 4, 6}, Σ ₂₂ = {2, 3, 8}, Σ ₂₃ = {5, 7}; состояние 9 выделяется в отдельный класс: {9}.

Шаг 3.

x(t) s(t)

s(t+1)

x(t) s(t)

s(t+1)

x(t) s(t)

s(t+1)

a1

a2

a3

a1

a2

a3

a1

a2

a3

Σ 21

Σ 22

Σ 21

Σ 21

Σ 22

Σ 21

Σ 21

Σ 23

Σ 23

Σ 21

Σ 21

Σ 22

Σ 22

Σ 21

Σ 21

Σ 21

Σ 21

Σ 23

Σ 21

Σ 21

Σ 22

Σ 22

{9}

Σ 21

Σ 21

Σ 21

Σ 23

Результат шага 3: Σ ₃₁ = {1, 4}, Σ ₃₂ = {2, 3, 8}, Σ ₃₃ = {5, 7}; {6}, {9}.

Шаг 4.

x(t) s(t)

s(t+1)

x(t) s(t)

s(t+1)

x(t) s(t)

s(t+1)

a1

a2

a3

a1

a2

a3

a1

a2

a3

Σ 31

Σ 32

Σ 31

Σ 31

Σ 32

2

Σ 31

Σ 31

Σ 33

Σ 33

{6}

Σ 31

Σ 32

Σ 32

Σ 31

Σ 31

Σ 31

{6}

Σ 33

{6}

Σ 31

Σ 32

Σ 31

Σ 31

Σ 33

Результат шага 4: Σ ₄₁ = {1, 4}, Σ ₄₂ = {2, 8}, Σ ₄₃ = {5, 7}; {3}, {6}, {9}.

Шаг 5.

x(t) s(t)

s(t+1)

x(t) s(t)

s(t+1)

x(t) s(t)

s(t+1)

a1

a2

a3

a1

a2

a3

a1

a2

a3

Σ 41

Σ 42

Σ 41

Σ 41

Σ 42

Σ 41

Σ 41

Σ 43

Σ 43

{6}

Σ 41

{3}

Σ 42

Σ 41

Σ 41

Σ 41

Σ 41

Σ 43

{6}

Σ 41

{3}

Результат шага 5: Σ ₅₁ = {1, 4}, Σ ₅₂ = {2, 8}, Σ ₅₃ = {5, 7}; {3}, {6}, {9} – совпадает с разбиением на шаге 4. Конец итераций.

Получены шесть классов эквивалентности: следовательно, автомат в минимальной форме имеет шесть состояний. Введем обозначения:

s⁽¹⁾ = {1, 4}, s⁽²⁾ = {2, 8}, s⁽³⁾ = {3}, s⁽⁴⁾ = {5, 7}, s⁽⁵⁾ = {6}, s⁽⁶⁾ = {9}.

Таблица переходов/выходов минимального автомата Ã имеет вид, показанный на рис. 7.2.

y(t)	s(t+1)
x(t) s(t)	a1	a2	a3	a1	a2	a3
s(1)				s(2)	s(1)	s(1)
s(2)				s(1)	s(1)	s(4)
s(3)				s(1)	s(5)	s(4)
s(4)				s(5)	s(1)	s(3)
s(5)				s(2)	s(6)	s(5)
s(6)				s(4)	s(6)	s(4)

Рис. 7.2. Таблица переходов/выходов минимального автомата Ã.

Фрагменты графов автоматов A и Ã представлены на рис. 7.3. Соответствия вершин показаны пунктиром.

Рис. 7.3. Фрагменты графов исходного и минимального автоматов.

Читателю предлагается самостоятельно проанализировать оба графа, сопоставить две картины инцидентности дуг вершинам, проставить веса дуг и убедиться в функциональной эквивалентности минимального и исходного автоматов.

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

1. Что такое класс конечных автоматов?

2. Какие автоматы относят к классу явно-минимальных? Явно-сократимых?

3. Какие конечные автоматы называют изоморфными?

4. Что такое эквивалентные состояния конечного автомата? Каковы их свойства?

5. Что такое эквивалентное разбиение конечного автомата?

6. Что называют минимальной формой автомата?

7. В чем состоит итерационный алгоритм Мили отыскания минимальной формы автомата?