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

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

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

- 1 0 - - 1 0 - -.

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

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

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

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

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

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

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

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

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

q₁	q₂	q₃	q₄	q₅	q₆
q₂-	q₃ 0	q₄ -	q₅ 1	-	-
q₃ 0	q₅ 0	q₆ -	q₃ 0	q₆ 0	─ 1
-	-	q₃ -	-	-	q₄ -
q₄ 0	-	-	q₁ -	-	q₂ -

Решение:

q₂	q₂ q₃ q₃ q₅
q₃	q₂q₄ q₃ q₆	q₃ q₄ q₅ q₆
q₄	q₂ q₅		q₄ q₅ q₃ q₆
q₅	q₃ q₆	q₅ q₆		q₃ q₆
q₆			q₃ q₄
	q₁	q₂	q₃	q₄	q₅

q₂
q₃	X	X
q₄		X
q₅		X
q₆	X	X		X	X
	q₁	q₂	q₃	q₄	q₅

q₂	X
q₃	X	X
q₄	X	X
q₅		X
q₆	X	X		X	X
	q₁	q₂	q₃	q₄	q₅

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

(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.

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

СИСТЕМА МНОЖЕСТВ	ШАГ
{ q₁q₂ q₃q₄ q₅q₆}
{ q₂q₃ q₄q₅ q₆}{ q₁q₅}
{ q₃q₄ q₅q₆}{ q₂}{ q₁q₅}
{ q₃q₄q₅q₆}{ q₂}{ q₁q₅}
{ q₃q₅ q₆}{ q₃q₄ q₅}{ q₂}{ q₁q₅}
{ q₃q₅}{ q₃q₆}{ q₃q₄ q₅}{ q₂}{ q₁q₅}

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