Mealyho automat

Z Wikipedie, otevřené encyklopedie

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.