Головна

Мінімізація абстрактного автомата Мура

  1. Питання 5. У яких висловлюваннях відзначаються особливості абстрактного мислення
  2. Для студентів, які не складуть зачета- «автомата» по синтаксису в V семестрі
  3. Мінімізація абстрактного автомата Мілі
  4. Мінімізація неповністю визначених перемикальних функцій.
  5. Мінімізація за допомогою мінімізують карт
  6. Мінімізація систем перемикальних функцій.

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

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

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

Приклад виконання двох початкових етапів мінімізації автомата Мура S14 наведено в таблиці 35 і таблиці 36.

Крок 3 Знаходження сумісних станів автомата Мура. Стану автомата Мура є 0-сумісними, якщо, беручи до уваги невизначених відміток, вони відзначені однаковими вихідними сигналами. Стану є i - сумісними для будь-якого i = 1, 2, ..., якщо вони 0-сумісні і автомат, переходячи з них, переробляє допустимі слова довжиною i однаково. Процедура розщеплення класів обов'язково закінчиться за обмежену кількість кроків і, отже, більш нерозщеплюваних класи утворюють кінцеві класи сумісних станів. Після знаходження сумісних станів автомата будується мінімізований нормалізований автомат Мура.

При табличному описі нормалізованого автомата Мура, що має Nn класів сумісних станів, перехід d (Ni, zj) Вважається невизначеним, якщо для всіх ai I Ni переходи d (ai, zj) Невизначені. Якщо хоча б для одного ai I Ni перехід d (ai, zj) Визначено, то в таблиці нормалізованого автомата вказується саме цей клас Nk, В який відбувається перехід. У часткового автомата таких переходів можливо кілька. Кожне клас Ni відзначається вихідним сигналом який відповідає всім станам цього класу.

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

Більш детально розглянемо застосування методики мінімізації автоматів Мура на прикладі повністю певного автомата S16.

Мінімізація абстрактного автомата Мілі | Елементарні автомати пам'яті


ВСТУП | Глава 1 | Базис І, АБО, НЕ. Властивості елементарних функцій алгебри логіки | Табличне опис булевих функцій | Аналітичний опис булевих функцій | Графічна форма подання булевих функцій | Геометричне уявлення булевих функцій | Мінімізація за допомогою мінімізують карт | Мінімізація функцій алгебри логіки методом Квайна | За методом Квайна - Мак-Класки |

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