Теоретичні основи мінімізації повністю визначених автоматів

У загальному випадку таблиця переходів ЦА, отримана тим або іншим способом, може містити надмірне число станів. Оскільки від кількості станів абстрактного автомата залежить число елементів пам'яті, які використовуються при структурному синтезі ЦА, то цілком обґрунтовано ставиться задача скорочення надмірних станів ЦА. При цьому процес мінімізації числа станів полягає у виключенні деяких станів абстрактного автомата, а також в заміні ряду станів одним так, щоб автомат, який вийшов в результаті, був еквівалентний початковому, тобто на однакову послідовність вхідних сигналів обидва автомати (початковий і мінімізований, що знаходяться в початковому стані) повинні відповідати однаковими послідовностями вихідних сигналів.

Проблему мінімізації кінцевих автоматів можна вирішувати в двох напрямах:

1. Мінімізація числа внутрішніх станів автоматів з метою скорочення

форми їх запису і побудови на мінімальній кількості елементів пам'яті.

2. Мінімізація автоматів з метою отримання оптимальніших (по відношенню певних критеріїв і в першій черзі в сенсі економічності) рішень в процесі їх технічної реалізації.

Перша постановка хоча і цілком коректна, але є обмеженою, так як містить елемент самоцілі. Він виходить з сумнівного твердження, що абстрактний автомат, який містить найменше можливе число внутрішніх станів, реалізується найекономічніше. Насправді складність, а в тій же час і вартість автомата, не рахуючи витрати на його проектування, визначаються числом та вартістю усіх технічних елементів, що становлять його схему. Практика показує, що у багатьох випадках мінімізація станів абстрактного автомата не призводить до зменшення вартості його технічній реалізації.

Загальнішою і строгішою є друга постановка завдання мінімізації автоматів. Її можна вважати завданням оптимального синтезу, оскільки чинник мінімальності (економічності) один з його постійних критеріїв. Алгоритми рішення задачі в такому плані (заданий автомат, загалом не мінімальний, вимагається знайти його економічну реалізацію) не публікувалися.

Завдання мінімізації внутрішніх станів кінцевого автомата полягає в знаходженні такого автомата, еквівалентного заданому, який має найменше число станів і найбільше число невизначених переходів (останнє тільки для не повністю визначених (часткових) автоматів).

Можливість скорочення числа станів визначається тим, що деякі внутрішні стани автомата, що означають як сумісні, можна об'єднувати в один стан, не порушуючи при цьому закону функціонування автомата.

При вирішенні цієї задачі використовуються деякі прийоми, що дозволяють проводити попереднє скорочення.

По-перше, з таблиці переходів можна видалити усі недосяжні стани, тобто такі, в які автомат не зможе потрапити з початкового стану під впливом будь-якої послідовності вхідних сигналів.

По-друге, з таблиці переходів автомата Мілі можна виключити усі стани, яким відповідають стовпці таблиці переходів, що містять у своїх клітинках тільки прочерки, тобто невизначені стани переходу. При цьому усі входження виключених за цим правилом станів в спрощеній таблиці переходів замінюються прочерками.

По-третє, з таблиці переходів автомата Мура можуть бути виключені усі стовпці, відповідні станам, відміченим невизначеними вихідними сигналами. Входження виключених станів в спрощену таблицю переходів замінюються прочерками.

Крім того, кожна група станів, якій відповідають однакові стовпці таблиці переходів, може бути замінена одним із станів групи, при цьому усі входження виключених станів в таблиці переходів замінюються на стан, номер якого представляє групу однакових стовпців.

Приклад. Сформуємо спрощену таблицю переходів автомата, заданого таблицею 1.17.

Таблиця 1.17 - Таблиця переходів автомата

У цій таблиці однакові стовпці відповідають станам (q₁, q₃) і (q₂, q₇). Введемо позначення: група станів (q₁, q₃) - 1, група (q₂, q₇) - 2.

Тоді стовпці таблиці, відповідні станам q₃ і q₇, можна виключити, а усі входження цих станів замінити станами q₁ і q₂ відповідно. В результаті отримаємо спрощену таблицю переходів (таблиця).

Таблиця 1.18 - Спрощена таблиця переходів