Введення в теорію цифрових автоматів, Мінімізація часткових автоматів
У попередньому розділі було описано алгоритм мінімізації числа станів повністю визначених автоматів, що ґрунтується на виявленні еквівалентних станів (спочатку 0-еквівалентних, потім 1-еквівалентних тощо). Цей алгоритм був заснований на ізоморфізмі алфавітних операторів до мінімізації і після неї, завдяки якому тільки можна було говорити про еквівалентність автоматів. Тепер, говорячи про часткові автомати, від цього доведеться відмовитися, оскільки області визначення автоматних функцій до мінімізації і після неї можуть не збігатися. Отже, мова може йти тільки про гомоморфізм мінімізованого автомата по відношенню до заданого, причому мінімізований автомат в одних випадках може бути цілком визначеним, а в інших – частковим. У разі остаточне довизначення автомата з його реалізації логічної мережею виробляється пізніше – на етапі структурного синтезу. При цьому доцільне довизначення часткових автоматних функцій дозволяє додатково покращувати результат мінімізації, так само, як це відбувається при мінімізації часткових логічних функцій.
Основний висновок зі сказаного у тому, що алгоритм мінімізації числа станів часткового автомата повинен грунтуватися не так на еквівалентності станів, але в їхсумісності. Сумісність ж повинна визначатися як здатність станів нового автомата забезпечувати ті ж наслідки, що і у вихідного автомата.
Із самого початку зробимо одне важливе застереження. Якщо у автомата Мілі функція переходів d(а, х) на деякій парі (а, х) не визначена, то це одночасно означає невизначеність значення на цій парі та функції виходів l(а, х). Раз дана пара значень аргументів є забороненою дляфункції переходів, то нема чого ставити на цій парі якесь певне значення функції виходів. Навіть якщо описується ймовірний останній крок роботи автомата, він повинен завершуватися в станіа0, щоб вийшов автомат багаторазової дії, готовий до нового циклу роботи.
Позбавлена сенсу та протилежна ситуація, коли функцію переходів визначено, а виходів – ні. Єдиний виняток, це вихід автомата Мура в початковому стані в моментt= 0. Але і в цьому випадку краще привласнити функції виходу значення «е», що означає порожню вихідну букву. Дане зауваження звільняє від необхідності розглядати зазначені надумані ситуації, що іноді робиться у спеціальній літературі з теорії автоматів.
Перейдемо до викладу алгоритму мінімізації часткових автоматів, заснованого виявленні сумісних станів (алгоритм Пола і Ангера). Розрізнятимемо два види сумісності станів:безумовнутаумовнусумісність. У табл. 4.19 наведено приклади безумовної сумісності станів автомата Милі.
Приклади безумовної сумісності станів автомата Мілі