Mealyho automat

V informatice se pojmem Mealyho stroj označuje konečný automat s výstupem. Výstup je generován na základě vstupu a stavu, ve kterém se automat nachází. To znamená, že stavový diagram automatu bude pro každý přechod obsahovat výstupní signál.

Mealyho stroje jsou obdobou Mooreových strojů, u těch ale výstup nezáleží na současném vstupu. I přesto je každý Mealyho stroj ekvivalentní nějakému Moorově stroji (jehož stavy jsou kartézský součin současných a předchozích stavů Mealyho stroje).

[editovat] Formální definice

Mealyho stroj je šestice (S, Σ, Λ, T, G, s), kde

• S je konečná množina stavů
• Σ je konečná vstupní abeceda
• Λ je konečná výstupní abeceda
• T je přechodová funkce (T : S × Σ → S)
• G je výstupní funkce (G : S × Σ → Λ)
• s ∈ S je počáteční stav

[editovat] Příklad

Tento stroj vypisuje vstup se zpožděním jednoho kroku, vygeneruje 0x₀x₁…x_n-1 pro vstup x₀x₁…x_n.
S₀ je počáteční stav.

[editovat] Převod Mealy -> Moore

[editovat] Mealy

[editovat] Moore

Rozšířím počet stavů

Vyškrtám nedosažitelné stavy a shodné stavy (zde shoda C2* s A1*)