1.2. Минимизация автоматов

Если состояния автомата эквивалентны, то они неразличимы между собой по реакции на любое входное слово. Автомат называется минимальным, если в нём нет эквивалентных состояний.

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

Задачу нахождения автомата, минимального заданному, называют задачей минимизации автомата.

1.2.1. Минимизация полностью определенного автомата

Назовём состояния a_m и a_S k-эквивалентными, если для них реакция на любое входное слово длиной не более k совпадают.

Тогда 1-эквивалентными будут те состояния, у которых реакция на любой символ входного алфавита одинакова, т.е. если у них одинаковые столбцы в матрице выходов.

Заменим в матрице переходов автомата имя состояния на имя блока в 1-эквивалентном разбиении. Сравним полученные столбцы для состояний в каждом блоке 1-эквивалентного разбиения. Проведём разбиение в каждом таком блоке по условию одинаковости столбцов. Получим разбиение на 2-эквивалентные состояния. Продолжим эту процедуру до тех пор, пока блоки к-эквивалентного разбиения не совпадут с блоками (к+1)-эквивалентного разбиения. В этом случае можно показать, что полученное разбиение будет разбиением на эквивалентные классы.

Пример. Пусть автомат описан табл.1.5.

Таблица 1.5
	1	2	3	4	5	6	7	8	9	10
z1	3/w1	6/w1	4/w1	1/w1	6/w1	3/w1	4/w1	10/w1	7/w1	9/w1
z2	2/w1	5/w2	7/w1	7/w2	3/w2	9/w2	3/w1	3/w2	6/w2	7/w2

Разбиение на 1-эквивалентные блоки имеет вид: b1 = (1, 3, 7), b2 = (2, 4, 5, 6, 8, 9, 10). По табл 1.5 построим переходы в блоки (b1, b2).

Таблица 1.6
	1	2	3	4	5	6	7	8	9	10
z1	b1	b2	b2	b1	b2	b1	b2	b2	b1	b2
z2	b2	b2	b1	b1	b1	b2	b1	b1	b2	b1

Разбиение на 2-эквивалентные состояния (по одинаковости столбцов в табл. 1.7) будет иметь вид: с1 = (1), с2 = (3, 7), с3 = (2), с4 = (4), с5 = (5, 8,10), с6 = (6,9). Построим переходы в блоки (с1-с6).

Таблица 1.7
	1	2	3	4	5	6	7	8	9	10
z1	с2	с6	с4	с1	с6	с2	с4	с5	с2	с6
z2	с3	с5	с2	с2	с2	с6	с2	с2	с6	с2

Разбиение на 3-эквивалентные состояния (см. табл.1.7) имеет вид: d1 = (1), d2 = (3,7), d3 = (2), d4 = (4), d5 = (5, 10), d6 = (8), d7 = (6, 9).

Переходы в блоки (d1-d7) представлены в табл. 1.8.

Таблица 1.8
	1	2	3	4	5	6	7	8	9	10
z1	d2	d7	d4	d1	d7	d2	d4	d5	d2	d7
z2	d3	d5	d2	d2	d2	d7	d2	d2	d7	d2

Разбиение на 4-эквивалентные состояния имеют вид: e1 = (1), e2 = (3,7), e3 = (2), e4 = (4), e5 = (5, 10), e6 = (8), e7 = (6, 9) и совпадают с 3-эквивалентными разбиениями. Значит минимальный автомат имеет 7 состояний, его таблица переходов-выходов представлена в табл 1.9.

Таблица 1.9
	d1	d2	d3	d4	d5	d6	d7
z1	d2/w1	d4/w1	d7/w1	d1/w1	d7/w1	d5/w1	d2/w1
z2	d3/w1	d2/w1	d5/w2	d2/w2	d2/w2	d2/w2	d7/w2