Автомат Мура

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

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

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

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

Скінченний автомат називається автоматом Мура, якщо його функція виходів залежить тільки від станів, тобто для будь-яких q , a_i , а_j, ${\displaystyle \lambda }$ ( q , a_i) = ${\displaystyle \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). (англ.)
• Karacuba A. A. Experimente mit Automaten (German) Elektron. Informationsverarb. Kybernetik, 11, 611–612 (1975). (нім.)
• Енциклопедія кібернетики