3.8. МИНИМИЗАЦИЯ ЧИСЛА СОСТОЯНИИ РАСПОЗНАЮЩЕГО АВТОМАТА

Минимизации числа состояний частичного автомата является важным процессом при проектировании координатора. Решению этой задачи посвящено большое количество работ, одиако полученные результаты часто далеки от непосредственного использовании в качестве практических программ для ЭВМ. При минимизации приходится учитывать следующее: число состояний является слишком большим и достигает нескольких сотен и даже тысяч; для практических целей совершенно необязательно получать абсолютно минимальное число состояний, поскольку, с одной стороны, практику устраивает достаточно близкое к оптимальному решение, с другой — нахождение минимального решения связано с таким объемом вычислений, который превосходит возможности современной вычислительной техники.

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

Обозначим через X, У, Z соответственно входной, выходной алфавит алфавит внутренних состояний частичного автомата Мили:

Будем считать, что синхронный автомат задай своими таблицами переходов (Z) и выходов (У). Совокупность этих двух таблиц будем называть таблицей переходов — выходов . Поскольку таблица переходов — выходов является частичной, т. е. не для каждой пары заданы значения , а лишь для векторного множества 21 входных последовательностей, доопределяя различными способами неопределенные элементы таблицы переходов — выходов, получим множество таблиц с эквивалентными на 21 функциональными свойствами, но с различным числом состояний.

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

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

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

таблицы на каждом шаге. При этом из множества вариантов выбирают оптимальный.

Будем говорить, что множество состояний Р влечет множество состояний Q (обозначим ), если для некоторого значения t входной переменной есть множество элементов , где k пробегает все значения из Р. Назовем цепью, производимой парой состояний , набор всех пар, удовлетворяющих следующим условиям: — первый член (звено) цепи, если пара ) является звеном цепи, то в эту же цепь должны входить все пары состоиний, которые влечет

Можно показать, что два состояния являются совместимыми в том и только в том случае, если в цепи, производимой нет ни одного звена такого, что при некотором если определены. Если при тех же условиях для некоторой пары то будем говорить, что состояния k и I имеют противоречие по таблице выходов (У) Цепь, образованную парами совместных состояний, назовем совместимой цепью.

Назовем одношаговым преобразованием исходной таблицы переходов—выходов переход к таблице с состояниями где состояние представляет пару состояний исходной таблицы характеризуют состояния исходной таблицы, не вошедшие в пары, образующие последовательность Элементам исходной матрицы присвоим верхний индекс «ноль», элементы новой матрицы оставим без индексов. Элементу придаем значение элемента если существует такое состояние представляемое состоянием s, для которого определен элемент в противном случае не определен. Элементу придается значение t, если и истинно высказывание:

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

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

Пример 1.

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

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

В таблице нельзя объединить никакие два состояния. Преобразования приводят к одному и тому же результату;

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

Однако далеко не всегда окончательный результат получается после применения одного преобразования. Чаще всего оказывается, что после того, как над таблицей с -состояниями произведено преобразование и получена новая таблица переходов — выходов с числом оостояний (мы не рассматриваем преобразований, не приводящих к сокращению числа состояний), к последней можно применить следующее преобразование и получить таблицу с числом состояний причем и т. д., пока не будет получена таблица в которой дальнейшее сокращение невозможно. Таким образом, окончательный результат получается после ряда последовательных преобразований (шагов), поэтому рассматриваемый метод можно назвать методом последовательных сокращений. Как показал опыт, этот метод особенно эффективен при минимизации матриц с большим числом состояний.

Если все звенья цепи, производимой парой состояний , s совместимы, то вычисляется сокращение числа состояний исходной матрицы, достигаемое при преобразовании по следующему правилу. Обозначим через Н число пар в цепи, через R — число различных состояний исходной матрицы, входящих в цепь. Тогда

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

Для оценки эффективности описанного алгоритма было проведено статистическое исследование и сравнение данного алгоритма с алгоритмом Пола и Ангера [25]. На ЭВМ случайным образом составлялись таблицы переходов — выходов, затем в этих таблицах минимизировалось число состояний по алгоритму

Пола—Ангера и по рассмотренному выше алгоритму. Результаты, полученные на выборке, содержащей около 300 таблиц, показали, что разность между средним числом состояний после минимизации по данному алгоритму и соответствующим числом, полученным по методу Пола — Ангера, не превосходит 0,45. Но среднее время решения одного примера в данном алгоритме, например для таблиц переходов—выходов с составило 3 с, а в алгоритме Пола — Ангера 25,5 с. Следует подчеркнуть, что сравнение производили лишь для таблиц с числом состояний не более 32, поскольку имеющаяся про грамма, реализующая метод Пола—Ангера, может работать с матрицами, число состояний которых не превосходит 32.