Mașina lui Mealy
Această intrare sau secțiune despre subiectul teoriilor informatice nu citează sursele necesare sau cei prezenți sunt insuficienți . |
În teoria calculabilității , mașina lui Mealy este un automat cu stare finită ale cărei valori de ieșire sunt determinate de starea curentă și de intrarea curentă, spre deosebire de mașina lui Moore , care în schimb funcționează doar ca o funcție a stării curente. Cu toate acestea, nu toate mașinile Mealy pot fi numite o mașină Moore echivalentă. Deoarece modelul Mealy bazează starea de ieșire a mașinii atât pe starea în care se află, cât și pe intrările pe care le primește mașina, în timp ce modelul Moore este valabil pentru mașinile care bazează ieșirea numai pe starea curentă a mașinii. indiferent de intrări.
Automatul își datorează numele promotorului său, americanul GH Mealy , care l-a descris în tratatul O metodă pentru sintetizarea circuitelor secvențiale din 1955 .
Mașina lui Mealy oferă un model matematic rudimentar pentru mașinile criptate . Folosind literele alfabetului latin pentru alfabetul de intrări și ieșiri, automatul poate lucra pe un șir dat de litere (adică o secvență de intrări) pe care le convertește într-un șir criptat (adică o secvență de ieșiri). Deși este posibil, de exemplu, să descriem Enigma printr-o mașină Mealy, diagrama de stare ar fi prea complicată pentru a înțelege cum funcționează mașinile criptate.
Definiție formală
O mașină Mealy este un sextuple , { S , S 0 , Σ, Λ, T , G }, format din:
- un set finit de stări ( S )
- o stare inițială S 0 , care este un element al lui ( S )
- un set finit numit alfabetul intrărilor (Σ)
- un set finit numit alfabetul rezultatelor (Λ)
- o funcție de tranziție ( T : S × Σ → S )
- o funcție de ieșire ( G : S × Σ → Λ)
Elemente conexe
Alte proiecte
-
Wikimedia Commons conține imagini sau alte fișiere despre Mașina lui Mealy
