Автомат Мура

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

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

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

Формальне визначення[ред.ред. код]

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

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

Способи задання[ред.ред. код]

  • Діаграма - зображений на площині орієнтований граф, вершини якого взаємно однозначно відповідають станам автомата, а дуги - вхідним символам. Вона пов'язує вихідне значення з кожним станом.
  • Таблиця переходів-виходів, в комірках якої для кожної пари значень аргументів х (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). (англ.)
  • Karatsuba A. A. List of research works (англ.)
  • Енциклопедія кібернетики