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 | uredi kôd]
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 × Σ → Λ)