Cтраница 4
При макроподходе минимизируют, как правило, число состояний автоматов, получая минимальные, или приведенные, автоматы. Специфика отыскания приведенных автоматов связана с формой задания автоматов и типа их поведения. Алгоритм минимизации состоит в построении такого автомата при том же способе задания, состояния к-рого соответствуют классам неотличимых состояний исходного автомата, а функции переходов и выходов определяются по представителям из этих классов. При этом минимальный автомат с точностью до изоморфизма состояний единствен. При рассмотрении конечного автомата как акцептора, представляющего подмножеством выделенных состояний событие, описанное с помощью заданного регулярного выражения, минимальный автомат строится эффективно, и алгоритм его построения можно разделить на два этапа. [46]
Весь набор состояний, покрываемых sk, содержится в полном списке совместимых классов. Все получающиеся таким образом совместимые классы образуют согласованное замкнутое множество. Если М минимален, то указанное множество содержит наименьшее возможное число элементов. Таких множеств совместимых классов может быть несколько. Все они приводят к минимальным автоматам, которые не обязаны быть изоморфными. [47]
Такой автомат может быть построен, напр. На втором этапе число состояний полученного автомата минимизируется обычным способом, причем классам неотличимых финальных состояний исходного автомата соответствуют финальные состояния минимального автомата. Аналогичным способом строится минимальный автомат, представляющий заданное сверхсобытие. Существуют единственные с точностью до изоморфизма состояний минимальные автоматы, представляющие заданные события и сверхсобытия. [48]
При макроподходе минимизируют, как правило, число состояний автоматов, получая минимальные, или приведенные, автоматы. Специфика отыскания приведенных автоматов связана с формой задания автоматов и типа их поведения. Алгоритм минимизации состоит в построении такого автомата при том же способе задания, состояния к-рого соответствуют классам неотличимых состояний исходного автомата, а функции переходов и выходов определяются по представителям из этих классов. При этом минимальный автомат с точностью до изоморфизма состояний единствен. При рассмотрении конечного автомата как акцептора, представляющего подмножеством выделенных состояний событие, описанное с помощью заданного регулярного выражения, минимальный автомат строится эффективно, и алгоритм его построения можно разделить на два этапа. [49]