Mealyev automat
U teoriji izračunljivosti, Mealyev automat (ili Mealyev stroj) je vrsta konačnog automata čija je funkcija izlaza pridružena trenutnom stanju i ulaznom znaku (simbolu). Slijedi da će odgovarajući dijagram stanja sadržavati i ulazni i izlazni znak za svaki brid (granu) prijelaza usmjerenog grafa. Kao suprotnost tome, izlaz Mooreovog konačnog automata ovisi isključivo o trenutnom stanju stroja, pri čemu prijelazi nemaju pridružen nikakav ulaz. Međutim, za svaki Mealyev automat postoji istovjetni Mooreov automat čiji je skup stanja unija skupa stanja Mealyevog automata i Kartezijevog produkta skupa stanja Mealyevog automata i ulazne abecede.
Ime "Mealyev automat" vuče korijene od svoga promicatelja: G. H. Mealya, jednog od pionira konačnih automata, koji ih je prvi opisao u radu A Method for Synthesizing Sequential Circuits, Bell System Tech. J. vol 34, pp. 1045–1079, September 1955.
Formalna definicija uredi
Mealyev automat je uređena šestorka, (S, S0, Σ, Λ, T, G), koju čine
- konačan skup stanja (S)
- početno (ili inicijalno) stanje S0 koje je element skupa (S)
- konačan skup ulaznih znakova (ulazna abeceda (Σ)
- konačan skup izlaznih znakova (izlazna abeceda) (Λ)
- funkcija prijelaza (T : S × Σ → S)
- izlazna funkcija (G : S × Σ → Λ)