![]() |
АВТОМАТОВ МИНИМИЗАЦИЯРасстановка ударений: АВТОМА`ТОВ МИНИМИЗА`ЦИЯ АВТОМАТОВ МИНИМИЗАЦИЯ - минимизация значений параметров автоматов, приводящая к эквивалентным и в определенном смысле оптимальным автоматам. Задача А. м. возникает при синтезе автоматов, и ее специфика зависит от подхода к их изучению.
При макроподходе минимизируют, как правило, число состояний автоматов, получая минимальные, или приведенные, автоматы. Специфика отыскания приведенных автоматов связана с формой задания автоматов и типа их поведения. Так, если в качестве поведения автомата конечного, заданного, напр., с помощью диаграммы переходов, рассматривать систему ограниченно-детерминированных функций, реализуемых автоматом, то отыскание минимального конечного автомата, эквивалентного исходному, осуществляется эффективно; оно основано на теореме Мура, согласно к-рой отличимость двух состояний автомата с n состояниями может быть установлена экспериментом длины n - 1. Алгоритм минимизации состоит в построении такого автомата при том же способе задания, состояния к-рого соответствуют классам неотличимых состояний исходного автомата, а функции переходов и выходов определяются по представителям из этих классов. При этом минимальный автомат с точностью до изоморфизма состояний единствен. При рассмотрении конечного автомата как акцептора, представляющего подмножеством выделенных состояний событие, описанное с помощью заданного регулярного выражения, минимальный автомат строится эффективно, и алгоритм его построения можно разделить на два этапа. Сначала по исходному регулярному выражению строится нек-рый, не обязательно минимальный, автомат, представляющий соответствующее регулярное событие. Такой автомат может быть построен, напр., с помощью индукции по операциям объединения ∪, конкатенации ○ и итерации ∗, входящим в регулярное выражение. По автоматам Для недетерминированных конечных, а также для недетерминированных и детерминированных бесконечных автоматов также существует единственный с точностью до изоморфизма состояний приведенный автомат. В первом случае отыскание этого автомата аналогично рассмотренному случаю конечных автоматов, а во втором его построение, вообще говоря, не является эффективным. Для стохастич. автомата с конечным числом состояний существует, вообще говоря, континуум различных приведенных автоматов, эквивалентных исходному. Отсюда следует отсутствие эффективного способа описания множества приведенных автоматов по заданному стохастич. автомату.
При микроподходе к изучению конечных автоматов для построения заданного автомата исходят из нек-рого конечного базисного набора Лит. см. при ст. Автомат конечный. В. А. Буевич. Источники:
|
![]()
|
|||
![]() |
|||||
© MATHEMLIB.RU, 2001-2021
При копировании материалов проекта обязательно ставить ссылку на страницу источник: http://mathemlib.ru/ 'Математическая библиотека' |