Автомат Мура

Автомат Мура (абстрактний автомат другого роду) в теорія обчислень — скінченний автомат, вихід якого залежить від його стану і не залежить прямо від його входу (на відміну від автомата Мілі), тобто $y(t)=\lambda (g(t))$ .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

Література

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 с.(рос.)

Це незавершена стаття з математики.
Ви можете допомогти проєкту, виправивши або дописавши її.