Milijeva mašina

U teoriji izračunljivosti, Milijeva mašina je konačan automat čije su izlazne vrednosti određene njenim trenutnim stanjem i trenutnim ulazom. (Ovo je u suprotnosti sa Murovom mašinom, čiji je izlaz u potpunosti određen njenim trenutnim stanjem.) Milijeva mašina je deterministički konačni transduktor. Za svako stanje i ulaz, postoji najviše jedan prelaz.

Istorijat

Milijeva mašina je dobila ime po Džordžu H. Miliju, koji je predstavio koncept 1955. godine, "Metoda za sintezu sekvencijalnih kola".

Formalna definicija

Milijeva mašina je uređena šestorka (Σ1, Σ2, Q, i, F, Δ) koja se sastoji od:

• konačnog skupa pod nazivom ulazni alfabet Σ1,
• konačnog skupa pod nazivom izlazni alfabet Σ2,
• konačnog skupa stanja Q,
• početnog stanja (inicijalnog stanja) i, koje je element skupa Q,
• konačnog skupa završnih stanja F, koji je potskup od Q i
• relacije prelaska Δ, koja je element skupa Q×Σ1×Σ2×Q i čije elemente nazivamo lukovima,

-Uvodimo funkciju prelaska i izlaznu funkciju:

• funkcija prelaska δ: Q×Σ1→Q koja preslikava par (stanje, ulazni simbol) u odgovarajuće sledeće stanje
• izlazna funkcija γ: Q×Σ1→Σ2, koja preslikava parove (stanje, ulazni simbol) u odgovarajući izlazni simbol.

U nekim formulacijama, funkcija prelaska i izlazna funkcija su sjedinjene u jednu funkciju: Q×Σ1→Q×Σ2

Poređenje Milijevih i Murovih mašina

1. I Murova i Milijeva mašina su vrste konačnog transduktora.
2. Svaka Murova mašina M je ekvivalentna Milijevoj mašini sa istim stanjima i prelascima i izlaznom funkcijom γ(p, a)=γM(p), gde je γM izlazna funkcija za M, p je stanje, a a slovo.
   • Ne može svaka Milijeva mašina da se konvertuje u odgovarajuću ekvivalentnu Murovu mašinu. Neke mogu da se konvertuju u skoro ekvivalentnu Murovu mašinu, kod koje su izlazi vremenski pomereni.
3. Najbitnija razlika između Milijeve i Murove mašine je u tome što je kod Milijeve mašine izlaz određen na osnovu trenutnog stanja i trenutnog ulaza, dok je kod Murove mašine isključivo na osnovu trenutnog stanja. Ako su predstavljene dijagramom:
   • kod Murove mašine, svaki čvor (stanje) je obeležen sa vrednosti na izlazu.
   • kod Milijeve mašine, svaki luk (prelaz) je obeležen sa vrednosti na izlazu.
4. Milijeve mašine teže ka manjem broju stanja.
5. Murove mašine su sigurnije za korišćenje.
   • Izlazi se menjaju nakon svakog ciklusa časovnika.
   • Kod Milijeve mašine, promena ulaza može uzrokovati promenu izlaza čim se izvrše logičke operacije- veliki problem kada su dve mašine međusobno povezane- može doći do asinhronizovanog odgovora.
6. Milijeve mašine brže reaguju na ulaz.
   • Kod Murovih mašina potrebno je više logičkih operacija da bi se stanje prevelo u izlaz.

Dijagram

Dijagram stanja za Milijevu mašinu povezuje izlaznu vrednost sa svakim prelazom (Ovo je u suprotnosti sa dijagramom stanja za Murovu mašinu, koji povezuje vrednost na ulazu sa svakim stanjem). Kada je Σ1=Σ2, Milijeva mašina se može predstaviti kao usmereni graf Q × Σ1, (p, a) → (δ(p, a), γ(p, a)). Temena ovog grafa su parovi (stanje, slovo), svaki čvor ima izlazni stepen 1, a sledbenik od (p, a) je sledeće stanje automata i slovo koje izbacuje automat kada je u stanju p i pročita sovo a.

Primeri

Prost automat

• Prosta Milijeva mašina ima jedan ulaz i jedan izlaz. Svaki prelaz je označen sa vrednosti na ulazu i vrednosti na izlazu. U prvom primeru, izlaz je ekskluzivna disjunkcija poslednje dve vrednosti sa ulaza. Mašina ispisuje 1 kad god dođe do promene vrednosti na ulazu, a 0 u suprotnom. Svaki prelaz određen je sa vrednosti na ulazu (predstavljeno crvenom bojom) i vrednosti na izlazu (predstavljeno plavom bojom na slici).

Primer ekskluzivne disjunkcije

• Neka je Σ1=Σ2={0, 1}, Q={0, 1, 2} i Δ={(0, 0, 0, 0), (0, 1, 0, 1), (1, 0, 0, 2), (1, 1, 1, 0), (2, 1, 1, 2), (2, 0, 1, 1)}. Konačan transduktor sa datom relacijom prelaska svakom binarnom broju dodeljuje količnik pri deljenju sa 3. Stanja datog transduktora su mogući ostaci prilikom deljenja nekog broja sa 3. Kada na binarni zapis trenutnog stanja nadovežemo tekuću vrednost sa ulaza i dobijeni binarni broj podelimo sa 3, ostatak pri tom deljenju je stanje u koje prelazimo. Prilikom svakog prelaska, transduktor na izlaz ispisuje i količnik. Ako je dati broj deljiv sa 3, čitanje sa ulaza će se završiti u stanju 0 (završno stanje), a ako nije, završiće se u nekom drugom stanju, koje predstavlja ostatak pri ovom deljenju.

Transduktor za deljenje sa 3 u binarnoj osnovi

Složen automat

Nešto složenije Milijeve mašine mogu imati više ulaza ili izlaza.

Primene Milijevih mašina

Milijeve mašine predstavljaju primitivni matematički model mašine za šifrovanje. Ako pretpostavimo da su ulazni i izlazni alfabet, na primer Latinica, onda Milijeva mašina može biti dizajnirana tako da prima nisku karaktera (kao ulaznu sekvencu) i prevodi je u šifrovanu nisku (kao izlaznu sekvencu).

Iako bi se modelom Milijeve mašine mogla opisati Enigma mašina, dijagram stanja bi bio suviše složen tako da ne bi bilo moguće obezbediti sredstva za dizajniranje takve mašine za šifrovanje.

Moderni procesori, računari, mobilni telefoni, digitalni satovi i osnovni elektronski uređaji imaju neku vrstu konačnog automata koji ih kontroliše.

Prosti softverski sistemi, naročito oni koji su predstavljeni korišćenjem regularnih izraza, napravljeni su po uzoru na konačan automat.

Postoje mnogi jednostavni primeri, kao što su automati za prodaju slatkiša ili osnovni elektronski sistemi.

Traženjem preseka dva konačna automata, mogu se dizajnirati veoma prosti konkurentni sistemi koji, na primer, razmenjuju poruke.

Semafor je sistem koji sadrži više podsistema kao što su različita svetla koja paralelno rade.

Još neki primeri

• klasifikacija brojeva
• sat sa tajmerom
• automat za prodaju slatkiša
• semafor
• skener bar kodova
• pumpe za gas

Literatura

• Mealy, George H. (1955). A Method for Synthesizing Sequential Circuits. Bell System Technical Journal. str. 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. str. 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 .