Построение минимального частичного автомата

Пусть имеется некоторая группировка состояний Q_1,Q_2,…,Q_S частичного автомата.

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

Имея замкнутую группировку Q_1,Q_2,…,Q_S из состояний частичного автомата М, можно построить покрывающий его автомат М’ аналогично тому, как это делалось для всюду определённых автоматов на основе классов эквивалентности. Для этого каждой группе совместимости Q_v в автомате M’ сопоставляется состояние . Состояние , в которое автомат переходит из под воздействием сигнала х, определяется группой Q_w. Если таких групп несколько, то можно взять любую из них.

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

Справедливо следующее утверждение: автомат М’ покрывает автомат М. Это связано с тем, что всякое состояние покрывается любым состоянием таким, что .

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

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

Таким образом, последовательность х₁,…,х_р окажется применимой к состоянию , а соответствующая выходная последовательность – совместимой с выходной последовательностью автомата М.

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

Действительно, рассмотрим произвольный автомат М’. Каждому его состоянию сопоставим множество Q_v всех покрываемых им состояний автомата М. Множество Q_v является группой совместимости, т.к. для любых состояний , любой применимой к ним последовательности , выходные последовательности совместимы. Это следует из того, что они покрываются выходной последовательностью автомата М’, возникающей при подаче в состояние . Совокупность всех групп Q_v образует группировку. Покажем её замкнутость. Рассмотрим произвольное состояние и входной сигнал х.

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

Таким образом установлено, что все состояния из Q_v под действием х переходят в состояния из множества Q_w. Это означает, что группировка замкнута.

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

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