покажемо зворотне твердження
Частково-определeнний (неповністю-определeнний) автомат - це автомат, у якого функції "l" і / або "d" визначені не повністю, значить, у нього вхідні слова можуть бути допустимими і не припустимими.
Два стану одного автомата називаються сумісними. якщо при подачі довільного слова на вхід автомата, що знаходиться в одному з цих станів, і в той же автомат, але знаходиться в іншому станів, на виході виходять несуперечливі слова, тобто збігаються там, де обидва визначені.
Властивості сумісності станів:
an (тобто немає транзитивності).
d (am, zi) = d (an, zi) для будь-якого zi з Z, (умова сумісності по переходу)
l (am, zi) = l (an, zi) для будь-якого zi з Z. (умова сумісності по виходу)
Класом сумісності станів C називають безліч станів, все елементи якого попарно сумісні один з одним.
Клас сумісності максимальний, якщо він не міститься повністю в іншому. Класом сумісності також є клас B = d (C, zi), якщо С - клас сумісності.
Завдання мінімізації часткового автомата S можна сформулювати як задачу пошуку автомата S ', який серед усіх автоматів, що покривають S, має найменше число станів. Першим кроком мінімізації автомата повинно бути видалення недосяжних станів, тобто станів, в які автомат не може перейти з початкового стану ні за яких вхідних словах. Далі процес мінімізації часткових автоматів включає в себе три основних етапи:
Знаходження всіх максимальних класів сумісності.
Знаходження мінімального замкнутого покриття.
Отримання за мінімальним замкнутому покриттю нового автомата.
Розглянемо алгоритм отримання сумісних пар за допомогою трикутної таблиці. запропонованої М.Поллом і С. Ангер. Розглядати будемо на прикладі автомата, заданого наступними таблицями переходів і виходів:
З цієї таблиці видно, що такі пари станів сумісні: (1, 2), (1, 4), (2, 3), (3, 4), (3, 5), (4, 5). А пари станів (1, 3), (1, 5), (2, 4), (2, 5) не сумісні. Тепер розглянемо спосіб знаходження максимальних класів сумісності з сумісних пар. Будемо говорити, що безліч станів В (В Í А) сумісно з деяким станом am Î A (позначення am
В), якщо і тільки якщо am
Алгоритм знаходження всіх максимальних класів сумісності зводиться до наступного:
Починаємо складання списку Ф класів сумісності з сумісних пар в крайньому правому стовпчику трикутної таблиці, що має принаймні одну клітку без хрестів. У прикладі Ф =>.
Просуваючись вліво, виписуємо для кожного i-го стовпця безліч станів А i
ai. тобто безліч всіх станів, відповідних клітин без хрестів в i -му стовпці таблиці. У нашому прикладі 3
(В третьому стовпці таблиці немає хрестів в рядках 4 та 5).
Кожне Аi перетинаємо з кожним членом поточного списку Ф. У нас А3 = і список Ф також містить єдиний елемент:
Якщо такий перетин містить більше одного стану, то додаємо в список об'єднання i> з результатом перетину:
Далі проводиться максимізація отриманого безлічі Ф - усунення всіх повторень множин в поточному списку і видалення всіх множин, що містяться в інших множинах списку:
Додаємо в список всі пари, що складаються з ai і різних станів з Аi. і не є підмножинами інших членів списку Ф (при i = 3 таких додавань немає).
Наведемо повністю результат застосування другого кроку до всіх стовпцях:
У список Ф, отриманий після другого кроку, додаються всі одноелементні множини, що складаються з станів, які не включені до жодної іншої максимальні класи сумісності (в нашому прикладі таких немає).
Очевидно, що результуючий список Ф є списком всіх максимальних класів сумісності. Таким чином, для автомата, розглянутого нами, безліч всіх класів сумісності
Другий етап - знаходження мінімального замкнутого покриття - досить складне завдання, що не представляє для нас особливого інтересу. Детальний опис цього алгоритму можна знайти в книзі С.І.Баранова "Синтез мікропрограмних автоматів". Ми ж в якості вихідного замкнутого покриття візьмемо безліч максимальних класів сумісності Ф = ,,,>.