Г л а в а 24

Минимизация частичных автоматов

24.1.Отношение реализации. Постановка задачи минимизации

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

Пусть задан частичный автомат М = (A, B, Q, Ψ, Φ).

допустимой для

Входная

последовательность

ai

ai

...ai

p

называется

1

2

состояния qi

автомата М, если

существует

последовательность состояний

1

) для 1 ≤ j ≤ p – 1

qi qi

2

...qi

p

, такая, что значение Φ(ai

p

,qi

p

)

и значения Ψ(ai

j

, qi

j

1

определены и Ψ(ai j ,qi j )= qi j+1 .

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

Состояние qj автомата М2 реализует состояние qi автомата М1, если любая входная последовательность, допустимая для qi, допустима и для qj, а отвечающие ей выходные последовательности, полученные от автомата М1 при начальном состоянии qi и от автомата М2 при начальном состоянии qj, совпадают везде, где выходы автомата М1 определены.

Отношение реализации, очевидно, является рефлексивным (любое состояние реализует само себя) и транзитивным (из того, что qi реализует qj, а qj реализует qk, следует, что qi реализует qk). Это отношение не является симметричным, т. е. из того, что qi реализует qj, не следует, что qj реализует qi. Симметричность не обеспечивается из-за того, что реализующее состояние может иметь более широкую область допустимых последовательностей, чем реализуемое состояние.

Автомат М2 реализует автомат М1, если для каждого состояния qi автомата М1 имеется по крайней мере одно состояние qj автомата М2, реализующее

158

состояние qi. Поведение автомата М2, реализующего автомат М1, совпадает с поведением автомата М1 везде, где поведение автомата М1 определено.

Задача минимизации частичного автомата ставится следующим образом: для заданного автомата М = (A, B, Q, Ψ, Φ) найти реализующий его автомат М′= (A, B, Q′, Ψ′, Φ′) с минимальным числом состояний.

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

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

совокупности.			{qr, qs, … , qt} Q
Некоторое	множество	состояний		назовем

непосредственно производным по входному символу а А множеством от множества состояний {qi, qj, … , qk} Q, если значения

Ψ(а, qj), Ψ(а, qj), … , Ψ(а, qk) составляют множество {qr, qs, … , qt}.

Для множества состояний {qr, qs, … , qt} непосредственно производным от него по входному символу а является множество тех состояний, в которые автомат переходит из состояний qr, qs, … , qt при поступлении на его вход символа а.

Множество состояний Qi Q называется непосредственно производным от Qj Q, если найдется такой входной символ а А, что Qi является непосредственно производным по а от Qj.

Группировка S называется правильной, если для каждого ее элемента Si справедливо следующее:

–любое непосредственно производное от него множество является подмножеством какого-то из элементов S;

–для любых qj, qk Si и для любого а А справедливо Φ(а, qj) = Φ(а, qk) всегда, когда эти значения оба определены.

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

Правильная группировка автомата М, имеющая минимальное число элементов среди всех правильных группировок автомата М, называется

минимальной.

От любой правильной группировки автомата М можно перейти к автомату М′, реализующему М, путем совмещения состояний, входящих в один и тот же элемент группировки. Если {qi, qj, … , qk} – элемент правильной группировки S

159

автомата М, то в автомате М′ ему соответствует состояние, реализующее любое из состояний qi, qj, … , qk. Если S – минимальная правильная группировка, то построенный по ней автомат М′ будет обладать минимальным числом состояний среди всех автоматов, реализующих автомат М.

Чтобы получить множество состояний Q′ автомата М′, надо каждому элементу Si S поставить в соответствие состояние q′i Q′. Функции Φ′ и Ψ′ получаются следующим образом.

Пусть q(i) – некоторое (любое) состояние автомата М, принадлежащее элементу Si S. Если Φ(а, q(i)) = b, то Φ′(а, q′i) = b. Если для всех q(i) из Si значение Φ(а, q(i)) не определено, то значение Φ′(а, q′i) считается

неопределенным.

Если значение Ψ(а, q(i)) не определено для всех q(i) Si, то Ψ(a, q′i) считается неопределенным. Обозначим символом Ψ(а, Si) множество, непосредственно производное от множества Si S по входному символу а (если значение Ψ(а, q(i)) не определено для всех q(i) Si, то Ψ(а, Si) = ). Тогда

Ψ(a, q′i) = q′j, где q′j соответствует любому Sj S, для которого Ψ(а, Si) Sj. Рассмотрим заимствованный из работы [20] пример построения автомата

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

автомата. Все два варианта доопределения				представлены в табл. 24.2 и
табл. 24.3.
Таблица 24.1					Таблица 24.2
Минимизируемый автомат				Вариант доопределения
1	а1	а2		1		а1	а2
	1,–	2,0				1,0	2,0
2	3,0	1,0		2		3,0	1,0
3	2,1	1,0		3		2,1	1,0

Нетрудно убедиться, что число состояний любого из этих полных автоматов не может быть уменьшено. В то же время множество S = {{1, 2}, {1, 3}} является правильной группировкой заданного автомата и табл.24.4 представляет таблицу переходов и выходов построенного по данной группировке автомата, реализующего заданный автомат. Число состояний полученного автомата меньше числа состояний исходного автомата.

Таблица 24.3				Таблица 24.4
Второй вариант доопределения				Результат минимизации
1	а1	а2		1	а1	а2
	1,1	2,0			2,0	1,0
2	3,0	1,0		2	1,1	1,0
3	2,1	1,0

160

24.2. Совместимость состояний

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

Отношение совместимости на множестве состояний автомата рефлексивно, симметрично, но не транзитивно. Из этих свойств отношение несовместимости обладает только симметричностью.

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

В некоторых случаях совместимость или несовместимость состояний устанавливается непосредственно. Пусть qi и qj – состояния некоторого автомата М. Если существует столбец таблицы выходов, в котором элементы строк qi и qj определены и различны, то состояния qi и qj несовместимы. Это

явно несовместимые состояния.

Если строки qi и qj таблицы переходов совпадают везде, где их элементы определены, и строки qi и qj таблицы выходов также совпадают везде, где их элементы определены, то состояния qi и qj совместимы. Это явно совместимые состояния.

Совместимость состояний qi и qj, которые не являются ни явно совместимыми, ни явно несовместимыми, определяется с помощью цепи, порождаемой парой состояний qi, qj , которая находится так же, как цепь для полного автомата.

Цепью, порождаемой парой состояний qi, qj частичного автомата М,

назовем множество С, элементами которого являются следующие пары

состояний: сама пара qi, qj ; все п ары вида Ψ(a, qk), Ψ(a, ql) , где Ψ(a, qk) и Ψ(a, ql) определены и различны, если qk, ql C. Другие пары не входят в С.

Справедливо следующее утверждение, которое доказывается точно так же, как утверждение 5.1.

У т в е р ж д е н и е 24.1.	Состояния qi	и qj	автомата М	являются
совместимыми, если и только	если в цепи,	порождаемой парой		состояний

qi, qj , нет ни одной пары явно несовместимых состояний. В этом случае все пары, принадлежащие данной цепи, являются парами совместимых состояний.

Совместимость удобно представлять булевой матрицей совместимости, строкам и столбцам которой соответствуют состояния автомата и элемент на пересечении i-й строки и j-го столбца имеет значение 1, если и только если состояния qi и qj совместимы. Процесс установления совместимости состояний

161

частичного автомата не отличается от процесса установления эквивалентности состояний полного автомата, описанного в разд. 5.2.

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

Таблица 24.5 Таблица переходов и выходов минимизируемого автомата

1	а1	а2	а3
	2,1	–,–	–,–
2	3,–	–,1	–,1
3	1,–	5,–	2,–
4	1,–	5,–	5,–
5	–,0	6,–	–,1
6	–,0	4,0	–,1

Явно несовместимыми являются пары 1, 5 , 1, 6 и 2, 6 . Пара 2, 5 является явно совместимой. Части цепей, порождаемых парами 1, 2 , 1, 4 ,

2, 4 , 3, 5 и 3, 6 ,	которые		необходимы		для		построения матрицы
совместимости, показаны на рис. 24.1.
1,2	1,4		2,4		3,5		3,6
2,3	1,2		1,3		5,6		4,5
1,3							4,6

4,5

Рис. 24.1. Части цепей для установления совместимости состояний

Формирование матрицы совместимости показано на примере следующей последовательности матриц:

2	3 4 5	6			2	3 4 5		6			2	3 4 5	6			2	3 4 5	6
	0 0		1		1 1		0 0		1		1 1 1 0 0			1		1 1 1 0 0			1
	1 0		2	,		1	1 0		2	,		1 1 0		2	,		1 1 1 0		2	,
			3						3					3					3
			4						4					4					4
			5						5					5					5

162