Автоматов минимизация

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

При макроподходе минимизируют, как правило, число состояний автоматов, получая минимальные, или приведенные, автоматы. Специфика отыскания приведенных автоматов связана с формой задания автоматов и типа их поведения. Так, если в качестве поведения автомата конечного, заданного, например, с помощью диаграммы переходов, рассматривать систему ограниченно-детерминированных функций, реализуемых автоматом, то отыскание минимального конечного автомата, эквивалентного исходному, осуществляется эффективно; оно основано на теореме Мура, согласно которой отличимость двух состояний автомата с n состояниями может быть установлена экспериментом длины n-1. Алгоритм минимизации состоит в построении такого автомата, при том же способе задания, состояния которого соответствуют классам неотличимых состояний исходного автомата, а функции переходов и выходов определяются по представителям из этих классов. При этом минимальный автомат с точностью до изоморфизма состояний единствен. При рассмотрении конечного автомата как акцептора, представляющего подмножеством выделенных состояний событие, описанное с помощью заданного регулярного выражения, минимальный автомат строится эффективно, и алгоритм его построения можно разделить на два этапа. Сначала по исходному регулярному выражению строится некоторый, не обязательно минимальный, автомат, представляющий соответствующее регулярное событие. Такой автомат может быть построен, например, с помощью индукции по операциям объединения U, конкатенации º и итерации *, входящим в регулярное выражение. По автоматам A₁, A₂ и A₃ и, представляющим, соответственно, события R₁, R₂ и R₃, специальным образом строятся автоматы A₄ , A₅ и A₆ , и, представляющие события R₁ U R₂, R₁ º R₂ и R₃* и, причем число состояний автомата A₄ не превосходит произведения чисел состояний автоматов А₁ и А₂; число состояний автомата А₅, вообще говоря, не больше произведения числа состояний автомата А₁ на число всех подмножеств множества состояний автомата А₂, а число состояний автомата А₆ не больше числа подмножеств множества состояний автомата А₃. На втором этапе число состояний полученного автомата минимизируется обычным способом, причем классам неотличимых финальных состояний исходного автомата соответствуют финальные состояния минимального автомата. Аналогичным способом строится минимальный автомат, представляющий заданное сверхсобытие. Существуют единственные с точностью до изоморфизма состояний минимальные автоматы, представляющие заданные события и сверхсобытия.

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

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

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