Милијева машина

Из Википедије, слободне енциклопедије
Иди на навигацију Иди на претрагу

У теорији израчунљивости, Милијева машина је коначан аутомат чије су излазне вредности одређене њеним тренутним стањем и тренутним улазом. (Ово је у супротности са Муровом машином, чији је излаз у потпуности одређен њеним тренутним стањем.) Милијева машина је детерминистички коначни трансдуктор. За свако стање и улаз, постоји највише један прелаз.

Историјат[уреди]

Милијева машина је добила име по Џорџу Х. Милију, који је представио концепт 1955. године, "Метода за синтезу секвенцијалних кола".[1]

Формална дефиниција[уреди]

Милијева машина је уређена шесторка (Σ1, Σ2, Q, i, F, Δ) која се састоји од:

  • коначног скупа под називом улазни алфабет Σ1,
  • коначног скупа под називом излазни алфабет Σ2,
  • коначног скупа стања Q,
  • почетног стања (иницијалног стања) i, које је елемент скупа Q,
  • коначног скупа завршних стања F, који је потскуп од Q и
  • релацијe преласка Δ, којa је елемент скупа Q×Σ1×Σ2×Q и чије елементе називамо луковима,

-Уводимо функцију преласка и излазну функцију:

  • функција преласка δ: Q×Σ1→Q која пресликава пар (стање, улазни симбол) у одговарајуће следеће стање
  • излазна функција γ: Q×Σ1→Σ2, која пресликава парове (стање, улазни симбол) у одговарајући излазни симбол.

У неким формулацијама, функција преласка и излазна функција су сједињене у једну функцију: Q×Σ1→Q×Σ2

Поређење Милијевих и Мурових машина[уреди]

  1. И Мурова и Милијева машина су врсте коначног трансдуктора.
  2. Свака Мурова машина М је еквивалентна Милијевој машини са истим стањима и преласцима и излазном функцијом γ(p, a)=γМ(p), где је γМ излазна функција за М, p је стање, а а слово.
    • Не може свака Милијева машина да се конвертује у одговарајућу еквивалентну Мурову машину. Неке могу да се конвертују у скоро еквивалентну Мурову машину, код које су излази временски померени.
  3. Најбитнија разлика између Милијеве и Мурове машине је у томе што је код Милијеве машине излаз одређен на основу тренутног стања и тренутног улаза, док је код Мурове машине искључиво на основу тренутног стања. Ако су представљене дијаграмом:
    • код Мурове машине, сваки чвор (стање) је обележен са вредности на излазу.
    • код Милијеве машине, сваки лук (прелаз) је обележен са вредности на излазу.
  4. Милијеве машине теже ка мањем броју стања.
  5. Мурове машине су сигурније за коришћење.
    • Излази се мењају након сваког циклуса часовника.
    • Код Милијеве машине, промена улаза може узроковати промену излаза чим се изврше логичке операције- велики проблем када су две машине међусобно повезане- може доћи до асинхронизованог одговора.
  6. Милијеве машине брже реагују на улаз.
    • Код Мурових машина потребно је више логичких операција да би се стање превело у излаз.


Дијаграм[уреди]

Дијаграм стања за Милијеву машину повезује излазну вредност са сваким прелазом (Ово је у супротности са дијаграмом стања за Мурову машину, који повезује вредност на улазу са сваким стањем). Када је Σ1=Σ2, Милијева машина се може представити као усмерени граф Q × Σ1, (p, a) → (δ(p, a), γ(p, a)). Темена овог графа су парови (стање, слово), сваки чвор има излазни степен 1, а следбеник од (p, a) је следеће стање аутомата и слово које избацује аутомат када је у стању p и прочита сово a.

Примери[уреди]

Прост аутомат
  • Проста Милијева машина има један улаз и један излаз. Сваки прелаз је означен са вредности на улазу и вредности на излазу. У првом примеру, излаз је ексклузивна дисјункција последње две вредности са улаза. Машина исписује 1 кад год дође до промене вредности на улазу, а 0 у супротном. Сваки прелаз одређен је са вредности на улазу (представљено црвеном бојом) и вредности на излазу (представљено плавом бојом на слици).
Пример ексклузивне дисјункције
  • Нека је Σ1=Σ2={0, 1}, Q={0, 1, 2} и Δ={(0, 0, 0, 0), (0, 1, 0, 1), (1, 0, 0, 2), (1, 1, 1, 0), (2, 1, 1, 2), (2, 0, 1, 1)}. Коначан трансдуктор са датом релацијом преласка сваком бинарном броју додељује количник при дељењу са 3. Стања датог трансдуктора су могући остаци приликом дељења неког броја са 3. Када на бинарни запис тренутног стања надовежемо текућу вредност са улаза и добијени бинарни број поделимо са 3, остатак при том дељењу је стање у које прелазимо. Приликом сваког преласка, трансдуктор на излаз исписује и количник. Ако је дати број дељив са 3, читање са улаза ће се завршити у стању 0 (завршно стање), а ако није, завршиће се у неком другом стању, које представља остатак при овом дељењу.
Трансдуктор за дељење са 3 у бинарној основи
Сложен аутомат

Нешто сложеније Милијеве машине могу имати више улаза или излаза.

Примене Милијевих машина[уреди]

Милијеве машине представљају примитивни математички модел машине за шифровање. Ако претпоставимо да су улазни и излазни алфабет, на пример Латиница, онда Милијева машина може бити дизајнирана тако да прима ниску карактера (као улазну секвенцу) и преводи је у шифровану ниску (као излазну секвенцу).

Иако би се моделом Милијеве машине могла описати Енигма машина, дијаграм стања би био сувише сложен тако да не би било могуће обезбедити средства за дизајнирање такве машине за шифровање.

Модерни процесори, рачунари, мобилни телефони, дигитални сатови и основни електронски уређаји имају неку врсту коначног аутомата који их контролише.

Прости софтверски системи, нарочито они који су представљени коришћењем регуларних израза, направљени су по узору на коначан аутомат.

Постоје многи једноставни примери, као што су аутомати за продају слаткиша или основни електронски системи.

Тражењем пресека два коначна аутомата, могу се дизајнирати веома прости конкурентни системи који, на пример, размењују поруке.

Семафор је систем који садржи више подсистема као што су различита светла која паралелно раде.

Још неки примери
  • класификација бројева
  • сат са тајмером
  • аутомат за продају слаткиша
  • семафор
  • скенер бар кодова
  • пумпе за гас

Референце[уреди]

  1. ^ Mealy, George H. (1955). „A Method for Synthesizing Sequential Circuits”. Bell System Technical Journal. 34: 1045—1079. doi:10.1002/j.1538-7305.1955.tb03788.x. 

Литература[уреди]

  • Mealy, George H. (1955). A Method for Synthesizing Sequential Circuits. Bell System Technical Journal. стр. 1045—1079. 
  • Holcombe, W.M.L. (1982). Algebraic automata theory. Cambridge Studies in Advanced Mathematics. 1. Cambridge University Press. ISBN 0-521-60492-3. Zbl 0489.68046. 
  • Roth, Charles H., Jr. (2004). Fundamentals of Logic Design. Thomson-Engineering. стр. 364—367. ISBN 0-534-37804-8. 
  • Akhavi, Ali; Klimann, Ines; Lombardy, Sylvain; Mairesse, Jean; Picantin, Matthieu (2012). „On the finiteness problem for automaton (semi)groups”. Int. J. Algebra Comput. 22 (6). Zbl 1280.20038. arXiv:1105.4725Слободан приступ.