На головну

мінімізація автоматів

  1.  Його Глос був досить гучним, тому деякі люди у сусідніх автоматів глянули на нас.
  2.  завдання автоматів
  3.  Закони функціонування автоматів.
  4.  Замкнені ланцюжка автоматів, «намальованих» один на одному
  5.  Мінімізація булевих функцій в класі ДНФ
  6.  Мінімізація висловлювань методом Квайна

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

До речі, перший розглянутий автомат був (свідомо) побудований надмірною. Від стану q3 дуже просто позбутися, передавши його функції станом q0.

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

Два автомата називаються еквівалентними, Якщо вони мають однакові вхідні і вихідні алфавіти, і на однакові вхідні слова видають однакові вихідні слова (однакової довжини).

Два стани називаються 1-еквівалентними, Якщо вони не помітні за допомогою одного вхідного сигналу (символу).

стани називаються k-еквівалентними, Якщо починаючи з них невиразні вхідні слова довжиною в k.

Якщо стану k-еквівалентні для будь-якого k, то вони називаються еквівалентними.

Розглянемо мінімізацію методом Гілла на якомусь конкретному автоматі Мілі.

 Т. В.
x1 y1 y1 y1 y1 y1 y2
x2 y2 y2 y2 y2 y2 y2

A B

 - I - еквівалентні

 Т. П.
x1  1 / A  3 / A  6 / B  2 / A  6 / B  4 / A
x2  2 / A  1 / A  3 / A  2 / A  5 / A  5 / A

 - II - еквівалентні

A B A B C

 A B C

 Т. П.
x1  1 / A  3 / A  6 / B  2 / C  6 / C  4 / A
x2  2 / A  1 / A  3 / A  2 / B  5 / B  5 / B

 - III - еквівалентні

A B C

 Т. П. A B C
x1 A C A
x2 A B B
 Т. В. A B C
x1 y1 y1 y2
x2 y y2 y2

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

Зауваження. Класи, в процесі їх виділення, можуть дробитися, але не можуть об'єднуватися.

Обмеженість методу Гілла. В отриманому автоматі наочно видно, що автомат не вийде з початкового стану А - воно є тупиковим.Отже, автомат ніколи не перейде в стан В і С, які в даному випадку будуть недосяжними.

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

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




 отримання диз'юнктів |  Аксіоматична теорія обчислення висловлювань |  Несуперечливість і повнота аксіоматичної теорії числення висловів |  Аксіоматичні теорії першого порядку |  система Генцен |  система Аристотеля |  Категоричні висловлювання. |  Модальні логіки. |  теорія Автоматів |  приклади автоматів |

© um.co.ua - учбові матеріали та реферати