Математическая энциклопедия » Что такое «Автоматов Минимизация»?

Значение слова, определение и толкование термина

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

Avtomatov Minimizatsiya

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

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

не обязательно минимальный, автомат, представляющий соответствующее регулярное событие. Такой автомат может быть построен, напр., с помощью индукции по операциям объединения [Автоматов Минимизация. Фото 1] конкатенации [Автоматов Минимизация. Фото 2] и итерации [Автоматов Минимизация. Фото 3] входящим в регулярное выражение. По автоматам [Автоматов Минимизация. Фото 4] представляющим, соответственно, события [Автоматов Минимизация. Фото 5], специальным образом строятся автоматы [Автоматов Минимизация. Фото 6] представляющие события [Автоматов Минимизация. Фото 7] причем число состояний автомата [Автоматов Минимизация. Фото 8] не превосходит произведения чисел состояний автоматов [Автоматов Минимизация. Фото 9] число состояний автомата [Автоматов Минимизация. Фото 10] вообще говоря, не больше произведения числа состояний автомата [Автоматов Минимизация. Фото 11] на число всех подмножеств множества состояний автомата [Автоматов Минимизация. Фото 12] а число состояний автомата [Автоматов Минимизация. Фото 13] не больше числа подмножеств множества состояний автомата [Автоматов Минимизация. Фото 14] На втором этапе число состояний полученного автомата минимизируется обычным способом, причем классам неотличимых финальных состояний исходного автомата соответствуют финальные состояния минимального автомата. Аналогичным способом строится минимальный автомат, представляющий заданное сверхсобытие. Существуют единственные с точностью до изоморфизма состояний минимальные автоматы, представляющие заданные события и сверхсобытия.

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

При микроподходе к изучению конечных автоматов для построения заданного автомата исходят из нек-рого конечного базисного набора [Автоматов Минимизация. Фото 15] логич. сетей. Требуется по автомату [Автоматов Минимизация. Фото 16] заданному, напр., с помощью канонич. уравнений, указать логич. сеть [Автоматов Минимизация. Фото 17], построенную из элементов базиса [Автоматов Минимизация. Фото 18] с использованием операций суперпозиции и обратной связи, к-рая реализует автомат [Автоматов Минимизация. Фото 19] и содержит минимальное число [Автоматов Минимизация. Фото 20] элементов базиса [Автоматов Минимизация. Фото 21] достаточное для реализации этого автомата. Т. о., сеть [Автоматов Минимизация. Фото 22] будет являться в этом смысле оптимальной схемой для автомата [Автоматов Минимизация. Фото 23] В общем случае задача о реализации произвольного автомата [Автоматов Минимизация. Фото 24] с помощью сетей над базисом [Автоматов Минимизация. Фото 25] неразрешима и, следовательно, функция сложности [Автоматов Минимизация. Фото 26] автомата [Автоматов Минимизация. Фото 27] невычислима. В случае же, когда известно, что базис [Автоматов Минимизация. Фото 28] является полным (см. Автоматов полные системы), построение любой оптимальной сети для [Автоматов Минимизация. Фото 29] может быть осуществлено эффективно, напр., следующим образом. Известно, что проверка реализуемости автомата [Автоматов Минимизация. Фото 30] с помощью заданной сети Sустанавливается эффективно. Кроме того, для заданного числа lчисло сетей над базисом [Автоматов Минимизация. Фото 31] сложности не более чем lвычислимо, и все эти сети строятся эффективно. Тем самым в качестве алгоритма построения всех оптимальных сетей для заданного автомата [Автоматов Минимизация. Фото 32] может быть использован последовательный просмотр на реализуемость автомата [Автоматов Минимизация. Фото 33] всех сетей сложности [Автоматов Минимизация. Фото 34] Вопрос о поведении функции [Автоматов Минимизация. Фото 35] и нек-рых ее обобщений составляет часть общей проблемы синтеза автоматов. Существует ряд эвристич. алгоритмов синтеза минимальных схем для автоматов, основанных на специальных свойствах базисов и конкретном содержании понятия оптимальности.

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

  • ВКонтакте

  • Facebook

  • Мой мир@mail.ru

  • Twitter

  • Одноклассники

  • Google+

См. также

  • (от греч. lipos - жир), жироподобные в-ва, входящие в состав всех живых клеток. Определение понятия липидов неоднозначно. Иногда к Л. относят люб

  • компактные звезды с массами порядка солнечной, радиусами Нейтронные звёзды10 км, состоящие в основном из нейтронов; конечный этап эволюции

  • — ветер, являющийся результатом воздействия рельефа местности и других особенностей подстилающей поверхности на общециркуляционное воз