Математическая энциклопедия - автоматов минимизация

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

При макроподходе минимизируют, как правило, число состояний автоматов, получая минимальные, или приведенные, автоматы. Специфика отыскания приведенных автоматов связана с формой задания автоматов и типа их поведения. Так, если в качестве поведения автомата конечного, заданного, напр., с помощью диаграммы переходов, рассматривать систему ограниченно-детерминированных функций, реализуемых автоматом, то отыскание минимального конечного автомата, эквивалентного исходному, осуществляется эффективно; оно основано на теореме М у-р а, согласно к-рой отличимость двух состояний автомата с псостояниями может быть установлена экспериментом длины n-1. Алгоритм минимизации состоит в построении такого автомата при том же способе задания, состояния к-рого соответствуют классам неотличимых состояний исходного автомата, а функции переходов и выходов определяются по представителям из этих классов. При этом минимальный автомат с точностью до изоморфизма состояний единствен. При рассмотрении конечного автомата как акцептора, представляющего подмножеством выделенных состояний событие, описанное с помощью заданного регулярного выражения, минимальный автомат строится эффективно, и алгоритм его построения можно разделить на два этапа. Сначала по исходному регулярному выражению строится нек-рый,

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

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

При микроподходе к изучению конечных автоматов для построения заданного автомата исходят из нек-рого конечного базисного набора логич. сетей. Требуется по автомату заданному, напр., с помощью канонич. уравнений, указать логич. сеть , построенную из элементов базиса с использованием операций суперпозиции и обратной связи, к-рая реализует автомат и содержит минимальное число элементов базиса достаточное для реализации этого автомата. Т. о., сеть будет являться в этом смысле оптимальной схемой для автомата В общем случае задача о реализации произвольного автомата с помощью сетей над базисом неразрешима и, следовательно, функция сложности автомата невычислима. В случае же, когда известно, что базис является полным (см. Автоматов полные системы), построение любой оптимальной сети для может быть осуществлено эффективно, напр., следующим образом. Известно, что проверка реализуемости автомата с помощью заданной сети Sустанавливается эффективно. Кроме того, для заданного числа lчисло сетей над базисом сложности не более чем lвычислимо, и все эти сети строятся эффективно. Тем самым в качестве алгоритма построения всех оптимальных сетей для заданного автомата может быть использован последовательный просмотр на реализуемость автомата всех сетей сложности Вопрос о поведении функции и нек-рых ее обобщений составляет часть общей проблемы синтеза автоматов. Существует ряд эвристич. алгоритмов синтеза минимальных схем для автоматов, основанных на специальных свойствах базисов и конкретном содержании понятия оптимальности.

Лит. см. при ст. Автомат конечный. В. А. Буевич.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985