TR | RU | KK | BE | EN |

Автомат Мура

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

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

Зміст

  • 1 Скінченний автомат Мура
  • 2 Формальне визначення
  • 3 Способи задання
  • 4 Зв'язок із машиною Мілі
  • 5 Приклад автомата Мура
  • 6 Реалізація кінцевого автомата Мура
  • 7 Див також
  • 8 Література

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

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

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

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

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

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

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

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

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

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

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

Кожна машина Мура М еквівалентна машині Мілі з тими ж станами та переходами, і вихідна функція, яка перетворює кожну вхідну пару станів 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, NJ1956 англ
  • 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 нім
  • Енциклопедія кібернетики


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

автомат муравейник, автомат муравьиная, автомат мураками, автомат мурат


Автомат Мура Інформацію Про

Автомат Мура


  • user icon

    Автомат Мура beatiful post thanks!

    29.10.2014


Автомат Мура
Автомат Мура
Автомат Мура Ви переглядаєте суб єкт.
Автомат Мура що, Автомат Мура хто, Автомат Мура опис

There are excerpts from wikipedia on this article and video

Випадкові Статті

Предводитель дворянства

Предводитель дворянства

Предводитель дворянства — впродовж 1766—1917 — обраний на губернських і повітових дворянсь...
Ханнес Хювенен

Ханнес Хювенен

Ханнес Хювенен фін Hannes Hyvönen; 29 серпня 1975, м Оулу, Фінляндія — фінський хокеїст, правий...
Віньоле-Борбера

Віньоле-Борбера

Віньоле-Борбера у Вікісховищі Віньоле-Борбера італ Vignole Borbera, п'єм Vigneule — мун...
Андрій Валентинов

Андрій Валентинов

Висловлювання у Вікіцитатах Андрі́й Валенти́нов, справжнє ім'я Андрі́й Валенти́нович Шмалько...