АВТОМАТИЧНО МИНИМИЗИРАНЕ
минимизиране на стойностите на параметрите на автоматите, което води до еквивалентни и в известен смисъл оптимални автомати. Проблемът за АМ възниква по време на синтеза на автомати и неговата специфика зависи от подхода към тяхното изследване.
При макро подхода, като правило, броят на състоянията на автоматите се минимизира, като се получават минимални или намалени автомати. Спецификата на намирането на редуцирани автомати е свързана с формата на специфициране на автоматите и вида на тяхното поведение. Така че, ако като поведениена краен автомат,дадено, например, с помощта на диаграма на преход, разглеждаме системаот ограничено детерминистични функции, реализирана от автомата, тогава търсенето на минимален краен автомат, еквивалентен на оригиналния, се извършва ефективно; основава се на теоремата на M y-ra, според която различимостта на две състояния на автомат с p-състояния може да се установи чрез експеримент с дължина n-1. Алгоритъмът за минимизиране се състои в конструирането на такъв автомат със същия метод на спецификация, чиито състояния съответстват на класове от неразличими състояния на оригиналния автомат, а преходните и изходните функции се определят от представители на тези класове. Освен това минималният автомат е уникален до изоморфизъм на състоянието. Когато разглеждаме краен автомат като акцептор, който представлява събитие, описано от даден регулярен израз като подмножество от избрани състояния, минималният автомат се конструира ефективно и алгоритъмът за неговото конструиране може да бъде разделен на два етапа. Първо, според оригиналния регулярен израз, определено
не непременно минимален, автомат, представляващ съответното редовно събитие. Такъв автомат може да бъде конструиран, например, чрез индукция върху операциите на обединяване на конкатенация и итерация, включени в регулярен израз. Чрез машинипредставляващи, съответно, събития, автоматите, представящи събития, са конструирани по специален начин и броят на състоянията на автомата не надвишава произведението на броя на състоянията на автомата, броят на състоянията на автомата, най-общо казано, не е по-голям от произведението на броя на състоянията на автомата по броя на всички подмножества на множеството от състояния на автомата, а броят на състоянията на автомата не е по-голям от броя на подмножествата на множеството на състоянията на автомата На втория етап броят на състоянията на получения автомат се минимизира по обичайния начин и класовете от неразличими крайни състояния на оригиналния автомат съответстват на крайните състояния на минималния автомат. По подобен начин се конструира минимален автомат, представящ дадено суперсъбитие. Съществуват уникални, до състояние на изоморфизъм, минимални автомати, представящи дадени събития и супер-събития.
За недетерминирани крайни автомати, както и за недетерминирани и детерминирани безкрайни автомати, също има уникален редуциран автомат до изоморфизъм на състоянието. В първия случай търсенето на този автомат е подобно на разглеждания случай на крайни автомати, а във втория конструкцията му, най-общо казано, не е ефективна. За стохастичен За автомат с краен брой състояния съществува, най-общо казано, континуум от различни редуцирани автомати, които са еквивалентни на оригиналния. Това предполага липсата на ефективен начин за описване на набор от редуцирани автомати за дадена стохастика. машина.
Лит.виж чл.Автоматичен край. В. А. Буевич.