Автомат Мура

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Електронна система як Автомат Мура

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

Таке визначення автомату вперше запропонував Едвард Форрест Мур, що опублікував свої дослідження в 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). (англ.)
  • Karacuba A. A. Experimente mit Automaten (German) Elektron. Informationsverarb. Kybernetik, 11, 611–612 (1975). (нім.)
  • Енциклопедія кібернетики