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

Електронна система як Автомат Мура

Таке визначення автомату вперше запропонував Едвард Форрест Мур, що опублікував свої дослідження в 1956 році у виданні «Gedanken-experiments on Sequential Machines.»

Скінченний автомат Мура

ред.

Скінченний автомат називається автоматом Мура, якщо його функція виходів залежить тільки від станів, тобто для будь-яких q , ai , аj,   ( q , ai) =   ( q , aj). Функцію виходів автомата Мура природно вважати одноаргументною функцією; зазвичай її позначають буквою m і називають функцією відміток (так як вона кожному стану однозначно ставить у відповідність позначку - вихід). У графі автомата Мура вихід зображається не на ребрах, а біля вершини.

Формальне визначення

ред.

Автомат Мура може бути визначений як кортеж з 6 елементів (S, S0, Σ, Λ, Т, G):

  • множина внутрішніх станів S (внутрішній алфавіт);
  • початковий стан S0,  який є елементом (S);
  • скінченна множина вхідних сигналів Σ (вхідний алфавіт);
  • скінченна множина вихідних сигналів Λ (вихідний алфавіт);
  • функція переходу (Т: S × Σ → S), яка відображає стан і вхідний алфавіт у наступний стан;
  • вихідна функція (G: S → Λ), яка відображає кожен стан у вихідний алфавіт.

Способи задання

ред.
  • Діаграма - зображений на площині орієнтований граф, вершини якого взаємно однозначно відповідають станам автомата, а дуги - вхідним символам. Вона пов'язує вихідне значення з кожним станом.
  • Таблиця переходів-виходів, в комірках якої для кожної пари значень аргументів х(t), s(t) проставляються майбутні внутрішні стани s(t+1). Значення вихідних сигналів y(t) представляються в окремому стовпці.

Зв'язок із машиною Мілі

ред.

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

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

  • у машині Мура кожен вузол (стан) позначений вихідним значенням;
  • у машині Мілі кожна дуга (перехід) позначена вихідним значенням.

Кожна машина Мура М еквівалентна машині Мілі з тими ж станами та переходами, і вихідна функція, яка перетворює кожну вхідну пару станів (Q, X) у GM (Q), де GM - вихідна функція машини М.

Приклад автомата Мура

ред.

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

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

Так, якщо об'єкт знаходиться в стані "анфас", то при виконанні команди направо він повинен показати нам свій лівий бік, тобто перейти в стан "зліва". Якщо повторити ту ж команду, то об'єкт перейде в стан "назад".

Реалізація скінченного автомата Мура

ред.

Блок-схема програми, яка реалізує поведінку автомата Мура.

 

Див. також

ред.

Література

ред.
  • Moore E. F. Gedanken-experiments on Sequential Machines. Automata Studies, Annals of Mathematical Studies, 34, 129–153. Princeton University Press, Princeton, N.J.(1956). (англ.)
  • Karatsuba A. A. Solution of one problem from the theory of finite automata. Usp. Mat. Nauk, 15:3, 157–159 (1960). (англ.)
  • Енциклопедія кібернетики
  • Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
  • Роджерс Х.(інші мови). Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)