Теорема:

Всякий минимальный автомат с точностью до переобозначения состояний совпадает с автоматом М^’, построенным по приведённому ранее алгоритму.

Доказательство:

1) Покажем, что автомат М^’ эквивалентен автомату М. Согласно определения эквивалентности автоматов, достаточно установить, что для каждого состояния q_i автомата М найдётся эквивалентное состояние автомата М’, и наоборот.

Эквивалентным состоянию q_i является состояние , соответствующее классу эквивалентностиQ_v, содержащему q_i. В качестве эквивалентного состоянию может быть взято любое состояние, входящее вQ_v. Покажем это:

Пусть автоматы М и М’ установлены в состояние исоответственно. На входы автоматов подаётся произвольная последовательность х₁,…,х_р. По правилу построения автомата М’ после считывания символа х₁ оба автомата выдадут одинаковый выходной символ. При этом автомат М перейдёт в состояние q_j, a M’ в состояние , причём.

Считывание второго символа х₂ снова приведёт к одинаковым выходным символам и переведёт автоматы в состояния q_k и , причём. И так далее.

Продолжив эти рассмотрения, можно убедиться в полном совпадении выходных последовательностей. Т.е. М и М’ эквивалентны.

2) Покажем, что автомат М^’ является минимальным.

Предположим противное: существует автомат М”, эквивалентный М и имеющий меньшее число состояний, чем М’. Т.к. эквивалентность является транзитивным отношением, то автоматы М” и М’ должны быть эквивалентными. Это означает, что для каждого состояния в автомате М’ имеется эквивалентное состояниеавтомата M”. Поскольку автомат M” имеет меньше состояний, чем М’, то некоторому состояниюэквивалентны, по крайней мере, 2 состояния. Это означает, что последние 2 состояния автомата М’ эквивалентны между собой, т.е. эквивалентны между собой будут все состояния автомата М из множеств. Это противоречит тому, что- различные классы эквивалентности.

3) Покажем, что любой минимальный автомат, с точностью до переобозначения состояний, совпадает с М’.

Рассмотрим произвольный минимальный автомат M’’. Согласно пункту 2 автоматы М’ и M’’ имеют одинаковое число состояний, причём для каждого состояния автомата М’ существует единственное эквивалентное ему состояние автомата М’’.

Переобозначим состояния автомата М’’ в соответствии с именами состояний автомата М’, чтобы состояние было эквивалентно состоянию.

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

Если автомат М’ перейдёт в состояние , то автомат М” должен оказаться в состоянии, иначе (если автомат М” перейдёт в состояние) в силу неэквивалентностиинайдётся некоторая входная последовательность х₁,…,х_р, подача которой, начиная с состояния и, приводит к неодинаковым выходным последовательностям.

Тогда последовательность х₁,…,х_р, применённая к состояниям и, также будет выдавать различные выходные последовательности, а это противоречит эквивалентности состоянийи. Поэтому мы заключаем, что автоматы М’ и М” совпадают с точностью до переобозначения состояний.

Совместимые состояния частичных автоматов

Последовательности и, составленные из символов некоторого алфавита и неопределённого символа “-”, называются совместимыми, если существует общая для них покрывающая последовательность. Другими словами, если в соответствующих позициях в последовательностяхирасположены значащие символы, то эти символы обязаны совпасть.

Например: совместимы 2 – 0 1 - - 0 1 2,

- 1 0 - - 1 0 - -.

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

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

Группа совместимости называется максимальной, если при добавлении к ней любого состояния она перестаёт быть группой совместимости.

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

Группировка, составленная из всех максимальных групп совместимости, называется максимальной.

Нахождение максимальной группировки

Максимальная группировка группируется на основе пар совместимых состояний. Для выявления таких пар может быть использован метод, применявшийся ранее для отыскания пар эквивалентных состояний. Т.е. строится треугольная таблица, из которой шаг за шагом вычёркиваются клетки. Невычеркнутые клетки результирующей таблицы соответствуют всем парам совместимых состояний.

Доказательство: самостоятельно.

Пример: задан частичный автомат

	q1	q2	q3	q4	q5	q6
0	q2 -	q3 0	q4 -	q5 1	-	-
1	q3 0	q5 0	q6 -	q3 0	q6 0	─ 1
2	-	-	q3 -	-	-	q4 -
3	q4 0	-	-	q1 -	-	q2 -

Решение:

q2	q2 q3 q3 q5
q3	q2 q4 q3 q6	q3 q4 q5 q6
q4	q2 q5			q4 q5 q3 q6
q5	q3 q6	q5 q6				q3 q6
q6				q3 q4
	q1	q2		q3		q4		q5

q2
q3	X	X
q4		X
q5		X
q6	X	X		X	X
	q 1	q2	q 3	q 4	q 5

q2	X
q3	X	X
q4	X	X
q5		X
q6	X	X		X	X
	q 1	q2	q 3	q 4	q 5

Из последней таблицы следует, что всеми парами совместимых состояний будут:

(q₁ q₅), (q₃ q₄), (q₃ q₅), (q₃ q₆), (q₄ q₅).

Построение максимальной группировки производится с использованием результирующей треугольной таблицы: на основе просмотра столбцов слева направо последовательно образуются некоторые системы множеств. В качестве исходной берётся система, состоящая из единственного множества – множества всех состояний.

Предположим, что после рассмотрения i-1 столбцов построена система множеств Q₁,Q₂,…,Q_p. При переходе к столбцу номер i рассматриваются все состояния, несовместимые с q_i, или соответствующие зачёркнутые клетки столбца.

Если множество Q_j не содержит одновременно состояние q_i и несовместимое с ним состояние, то это множество не изменяется, иначе из множества Q_j образуется 2 множества: одно получается удалением состояния q_i, другое – удалением всех состояний, несовместимых с q_i. Проделав такую операцию для всех множеств Q_j и устранив немаксимальные множества (те, которые содержатся в других), мы получим систему множеств, которая является результатом шага i.

Совокупность множеств, образованная после просмотра последнего столбца треугольной таблицы, является максимальной группировкой.

СИСТЕМА МНОЖЕСТВ	ШАГ
{ q1 q2 q3 q4 q5 q6}	0
{ q2 q3 q4 q5 q6 }{ q1 q5}	1
{ q3 q4 q5 q6}{ q2 }{ q1 q5}	2
{ q3 q4 q5 q6}{ q2 }{ q1 q5}	3
{ q3 q5 q6 }{ q3 q4 q5}{ q2}{ q1 q5}	4
{q3 q5}{ q3 q6}{ q3 q4 q5 }{ q2 }{ q1 q5}	5

Подмножество