Автомат Мілі: відмінності між версіями

[неперевірена версія][перевірена версія]
(Створена сторінка: thumb|169px|[[Абстрактного автомата граф|Діаграма станів для простого автомата Міл...)
 
(Bluelink 1 book for Перевірність (20220301)) #IABot (v2.0.8.6) (GreenC bot)
 
(Не показані 16 проміжних версій 14 користувачів)
Рядок 1: Рядок 1:
[[Image:Mealy.png|thumb|169px|[[Абстрактного автомата граф|Діаграма станів]] для простого автомата Мілі, з одним входом та одним виходом. Кожен перехід відмічений вхідним (червоний) та вихідним (синій) символами. Автомат починає роботу в стані S<sub>i</sub>. (В цьому прикладі автомат дає на виході [[XOR]], двох останніх вхідних символів, тобто одиничку, якщо останній вхідний символ відрізнявся від попереднього він виводить одиничку. Більш складні автомати Мілі можуть мати багато входів та багато виходів.]]
[[Файл:Mealy.png|thumb|400px|[[Абстрактного автомата граф|Діаграма станів]] для простого автомата Мілі, з одним входом та одним виходом. Кожен перехід відмічений вхідним (червоний) та вихідним (синій) символами. Автомат починає роботу в стані S<sub>i</sub>. (В цьому прикладі автомат дає на виході [[XOR]], двох останніх вхідних символів, тобто одиничку, якщо останній вхідний символ відрізнявся від попереднього він виводить одиничку. Складніші автомати Мілі можуть мати багато входів та багато виходів.]]


'''Автомат Мілі''' - [[скінченний автомат]] чиї вихідні символи визначаються його станом, та символами на вході (на відміну від [[Автомат Мура|автомату Мура]] вихідні символи якого визначаються тільки його станом). На ребрах в [[діаграма станів|діаграмі станів]] позначають вхідні та вихідні символи (а в автоматі Мура вихідні символи позначають на вершинах).
'''Автомат Мілі'''&nbsp;— [[скінченний автомат]] чиї вихідні символи визначаються його станом, та символами на вході (на відміну від [[Автомат Мура|автомату Мура]] вихідні символи якого визначаються тільки його станом). На ребрах в [[діаграма станів|діаграмі станів]] позначають вхідні та вихідні символи (а в автоматі Мура вихідні символи позначають на вершинах).

Автомат Мілі названий на честь Джорджа Мілі, який представив ідею в роботі 1955 року, “A Method for Synthesizing Sequential Circuits.<ref>{{cite journal| last=Mealy| first=George H.| title=A Method for Synthesizing Sequential Circuits| journal=Bell Systems Technical Journal| volume=34| pages=1045–1079| month=September| year=1955}}</ref>


Автомат Мілі названий на честь Джорджа Мілі, який представив ідею в роботі 1955 року, «A Method for Synthesizing Sequential Circuits.»<ref>{{cite journal| last=Mealy| first=George H.| title=A Method for Synthesizing Sequential Circuits| journal=Bell Systems Technical Journal| volume=34| pages=1045–1079| month=September| year=1955}}</ref>


Автомат Мілі може бути примітивною математичною моделлю шифрувальної машини. Якщо взяти за вхідний та вихідний алфавіти наприклад символи [[Латинська абетка|латинки]], то можна сконструювати автомат Мілі, який буде для кожного вхідного рядка давати на виході зашифровану послідовність. Тим не менш, хоча його й можна використати для опису наприклад шифрувальної машини [[Енігма (автомат)|Енігма]], діаграма станів буде занадто складною для конструювання відповідного автомата.
Автомат Мілі може бути примітивною математичною моделлю шифрувальної машини. Якщо взяти за вхідний та вихідний алфавіти наприклад символи [[Латинська абетка|латинки]], то можна сконструювати автомат Мілі, який буде для кожного вхідного рядка давати на виході зашифровану послідовність. Тим не менш, хоча його й можна використати для опису наприклад шифрувальної машини [[Енігма (автомат)|Енігма]], діаграма станів буде занадто складною для конструювання відповідного автомата.


== Формальне означення ==
== Формальне означення ==
Автома Мілі це [[кортеж|шестірка]], (''S'', ''S''<sub>0</sub>, X, Y, ''T'', ''G''), що складається з:
Автомат Мілі це [[кортеж|шестірка]], (''S'', ''S''<sub>0</sub>, X, Y, ''T'', ''G''), що складається з:
* скінченної множини станів (''S'')
* скінченної множини станів (''S'')
* початкового (ініціального) стану ''S''<sub>0</sub> який є елементом (''S'')
* початкового (ініціального) стану ''S''<sub>0</sub> який є елементом (''S'')
* вхідного алфавіту (X)
* вхідного алфавіту (X)
* вихідного алфавіту (Y)
* вихідного алфавіту (Y)
* [[Функція (математика)|функції]] переходів (''T'' : ''S'' × X → ''S'') що відображує пару стан, вхідний символ, на інший стан в який здійснюється перехід за цим символом.
* [[Функція (математика)|функції]] переходів (''T'' : ''S'' × X → ''S'') що відображує пару стан, вхідний символ, на інший стан в який здійснюється перехід за цим символом.
* [[Функція (математика)|функції]] виходів (''G'' : ''S'' × X → Y), яка відображає пари стан, вхідний символ, у вихідні символи.
* [[Функція (математика)|функції]] виходів (''G'' : ''S'' × X → Y), яка відображає пари стан, вхідний символ, у вихідні символи.


В деяких формулювання функції переходів та виходів об'єднують в одну (''T'' : ''S'' × X → ''S'' × Y).
В деяких формулювання функції переходів та виходів об'єднують в одну (''T'' : ''S'' × X → ''S'' × Y).


== Дивись також ==
== Див. також ==
* [[Автомат Мура]]
* [[Автомат Мура]]
* [[Автоматні відображення]]


== Зноски ==
== Примітки ==
{{Reflist}}
{{Reflist}}


== Посилання ==
== Посилання ==
* {{cite book
* {{en|http://en.wikipedia.org/wiki/Mealy_machine}}
*{{cite book
| last = Mealy
| last = Mealy
| first = George H.
| first = George H.
Рядок 35: Рядок 34:
| pages = 1045–1079
| pages = 1045–1079
}}
}}
* {{cite book

*{{cite book
| last = Roth
| last = Roth
| first = Charles H., Jr.
| first = Charles H., Jr.
| title = Fundamentals of Logic Design
| title = Fundamentals of Logic Design
| url = https://archive.org/details/isbn_9780534384432
| publisher = Thomson-Engineering
| publisher = Thomson-Engineering
| date = 2004
| date = 2004
Рядок 45: Рядок 44:
| isbn = 0534378048
| isbn = 0534378048
}}
}}
[[Категорія:Теорія автоматів]]

[[Категорія:Скінченні автомати]]
[[Категорія:Скінченні автомати]]

[[bs:Mealyjev automat]]
[[ca:Màquina de Mealy]]
[[cs:Mealyho automat]]
[[de:Mealy-Automat]]
[[es:Máquina de Mealy]]
[[fr:Machine de Mealy]]
[[hr:Mealyev automat]]
[[id:Mesin Mealy]]
[[it:Macchina di Mealy]]
[[ja:ミーリ・マシン]]
[[pl:Automat Mealy'ego]]
[[pt:Máquina de Mealy]]
[[ru:Автомат Мили]]
[[th:เครื่องจักรแบบเมลลี่]]
[[zh:米利型有限状态机]]

Поточна версія на 02:36, 2 березня 2022

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

Діаграма станів для простого автомата Мілі, з одним входом та одним виходом. Кожен перехід відмічений вхідним (червоний) та вихідним (синій) символами. Автомат починає роботу в стані Si. (В цьому прикладі автомат дає на виході XOR, двох останніх вхідних символів, тобто одиничку, якщо останній вхідний символ відрізнявся від попереднього він виводить одиничку. Складніші автомати Мілі можуть мати багато входів та багато виходів.

Автомат Мілі названий на честь Джорджа Мілі, який представив ідею в роботі 1955 року, «A Method for Synthesizing Sequential Circuits.»[1]

Автомат Мілі може бути примітивною математичною моделлю шифрувальної машини. Якщо взяти за вхідний та вихідний алфавіти наприклад символи латинки, то можна сконструювати автомат Мілі, який буде для кожного вхідного рядка давати на виході зашифровану послідовність. Тим не менш, хоча його й можна використати для опису наприклад шифрувальної машини Енігма, діаграма станів буде занадто складною для конструювання відповідного автомата.

Формальне означенняРедагувати

Автомат Мілі це шестірка, (S, S0, X, Y, T, G), що складається з:

  • скінченної множини станів (S)
  • початкового (ініціального) стану S0 який є елементом (S)
  • вхідного алфавіту (X)
  • вихідного алфавіту (Y)
  • функції переходів (T : S × X → S) що відображує пару стан, вхідний символ, на інший стан в який здійснюється перехід за цим символом.
  • функції виходів (G : S × X → Y), яка відображає пари стан, вхідний символ, у вихідні символи.

В деяких формулювання функції переходів та виходів об'єднують в одну (T : S × X → S × Y).

Див. такожРедагувати

ПриміткиРедагувати

  1. Mealy, George H. (September 1955). A Method for Synthesizing Sequential Circuits. Bell Systems Technical Journal 34: 1045–1079. 

ПосиланняРедагувати

  • Mealy, George H. (1955). A Method to Synthesizing Sequential Circuits. Bell Systems Technical Journal. с. 1045–1079. 
  • Roth, Charles H., Jr. (2004). Fundamentals of Logic Design. Thomson-Engineering. с. 364–367. ISBN 0534378048.