Автомат Мура
Автомати Мура
В теорії обчислень автомат Мура — це тип кінцевого автомата, у якому вихідний сигнал залежить лише від його поточного стану, а не від вхідних даних. Ця характеристика відрізняє автомати Мура від автоматів Мілі, у яких вихідний сигнал залежить як від стану, так і від вхідних даних.
Формальне визначення
Автомат Мура формально визначається як 5-кортеж (Q, Σ, Г, δ, λ), де:
- Q — скінченна множина станів
- Σ — скінченна множина вхідних символів
- Г — скінченна множина вихідних символів
- δ: Q × Σ → Q — функція переходу
- λ: Q → Г — функція виходу
Основні відмінності від автоматів Мілі
Основною відмінністю між автоматами Мура та Мілі є залежність вихідного сигналу від стану та вхідних даних. В автоматах Мура вихідний сигнал визначається лише поточним станом автомата, а в автоматах Мілі його визначають як стан, так і вхідна послідовність.
Графічне зображення
Автомати Мура часто зображуються за допомогою графів станів, де:
- Вершини представляють стани
- Ребра представляють переходи, позначені парами (вхідний символ, вихідний символ)
- Початковий стан позначено однією вхідною стрілкою
- Кінцеві стани позначено подвійним колом
Приклади
Розглянемо приклад автомата Мура, який зчитує двійкову послідовність і виводить логічне значення істинності ("1"), якщо послідовність містить рівну кількість нулів та одиниць.
Стани: {S0, S1}
Вхідні символи: {0, 1}
Вихідні символи: {0, 1}
Функція переходу:
S0: 0 → S0
S0: 1 → S1
S1: 0 → S1
S1: 1 → S0
Функція виходу:
S0: λ → 0
S1: λ → 1
Застосування
Автомати Мура мають численні застосування, зокрема:
- Розпізнавання мов
- Створення логічних схем
- Проєктування контролерів
Автомат Мура — це тип кінцевого автомата, вихідний сигнал якого залежить лише від його поточного стану, а не від вхідних даних. Його можна використовувати для розпізнавання мов, створення логічних схем і проєктування контролерів. Він відрізняється від автомата Мілі тим, що його вихідний сигнал залежить тільки від стану.
Часто задавані запитання
- Що таке автомат Мура?
Автомат Мура — це тип кінцевого автомата, вихідний сигнал якого залежить лише від його поточного стану.
- Чим автомати Мура відрізняються від автоматів Мілі?
Автомати Мура залежать лише від стану для обчислення вихідного сигналу, тоді як автомати Мілі залежать як від стану, так і від вхідних даних.
- Навіщо використовуються автомати Мура?
Автомати Мура використовуються для розпізнавання мов, створення логічних схем і проєктування контролерів.
- Як зображаються автомати Мура?
Автомати Мура зазвичай зображуються за допомогою графів станів із позначеними краями.
- Які переваги автоматів Мура?
Автомати Мура прості в проєктуванні та аналізі завдяки своїй залежності лише від поточного стану.
Опубліковано