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

Mealyev automat je uređena šestorka, (S, S₀, Σしぐま, Λらむだ, T, G), koju čine

• konačan skup stanja (S)
• početno (ili inicijalno) stanje S₀ 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 × Σしぐま → Λらむだ)

Vidjeti također

• Mooreov automat