Mașina lui Moore

Diagrama de stare a mașinii lui Moore cu intrările x , y și z și ieșirile a , b și c .

În teoria calculabilității , mașina lui Moore este un automat cu stare finită în care ieșirile sunt determinate numai în funcție de stările curente (și nu și de stările de intrare, așa cum se întâmplă în schimb în mașina Mealy ). Diagrama de stare a unei mașini Moore oferă un semnal de ieșire pentru fiecare stare. Automatul își datorează numele promotorului său, americanul Edward F. Moore , profesor de matematică și informatică la Universitatea din Wisconsin-Madison, care l-a descris în tratatul Gedanken-experiments on Sequential Machines .

Majoritatea sistemelor electronice digitale sunt concepute ca sisteme de ceas de impuls secvențial, care sunt o formă redusă a mașinii lui Moore, în care starea se schimbă numai pe măsură ce se schimbă semnalul de ceas global. În general, starea curentă este salvată în flip-flop-uri , în timp ce semnalul global de ceas este conectat la intrarea flip-flop rezervată pentru ceas. Sistemele secvențiale cu ceas de impulsuri sunt doar o modalitate de a rezolva problemele de metastabilitate . O mașină electronică tipică Moore include o secvență logică combinatorie pentru a decoda starea curentă în ieșiri (lambda). Când starea curentă este modificată, schimbarea afectează întreaga secvență, schimbând (sau nu) aproape instantaneu și ieșirile. Există mai multe tehnici de proiectare care tind să limiteze orice erori în perioada scurtă de modificare, dar majoritatea sistemelor sunt construite în așa fel încât aceste „găuri” sunt fie ignorate, fie considerate irelevante. Ieșirile își păstrează starea la nesfârșit, atâta timp cât mașina nu schimbă starea din nou.

Definiție formală

O mașină Moore poate fi definită ca un sextuple $(S,S_{0},\Sigma ,\Lambda ,T,G)$ ${\ displaystyle (S, S_ {0}, \ Sigma, \ Lambda, T, G)}$ ${\ displaystyle (S, S_ {0}, \ Sigma, \ Lambda, T, G)}$ constând din:

un set finit de stări $S.$ ${\ displaystyle S}$ $S.$
o stare inițială $S_{0}$ ${\ displaystyle S_ {0}}$ $S_0$ care aparține $S.$ ${\ displaystyle S}$ $S.$
un set finit numit alfabet de intrare $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$
un set finit numit alfabetul de ieșire $\Lambda$ ${\ displaystyle \ Lambda}$ $\ Lambda$
o funcție de tranziție $T:S\times \Sigma \rightarrow S$ ${\ displaystyle T: S \ times \ Sigma \ rightarrow S}$ ${\ displaystyle T: S \ times \ Sigma \ rightarrow S}$ care mapează o stare și o intrare în următoarea stare
o funcție de transformare sau o funcție de ieșire, $G:S\rightarrow \Lambda$ ${\ displaystyle G: S \ rightarrow \ Lambda}$ ${\ displaystyle G: S \ rightarrow \ Lambda}$ care mapează fiecare stare în alfabetul ieșirilor

Există o definiție a unei mașini echivalentă cu cea anterioară și este mașina Mealy, în care funcția de ieșire este definită ca $G:S\times \Sigma \rightarrow \Lambda$ ${\ displaystyle G: S \ times \ Sigma \ rightarrow \ Lambda}$ ${\ displaystyle G: S \ times \ Sigma \ rightarrow \ Lambda}$ , care mapează o stare și o intrare la ieșire. Diversitatea în definiția funcției de ieșire duce la presupunerea că numărul de stări într-o mașină Moore va fi mai mare sau egal cu numărul de stări ale mașinii echivalente Mealy (constatabil în mod trivial din faptul că trebuie să existe stări diferite care iau în considerare implicit diferitele intrări).

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere despre Mașina lui Moore