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 × Σ → Λ)
  • sS je počáteční stav

[editovat] Příklad

Tento stroj vypisuje vstup se zpožděním jednoho kroku, vygeneruje 0x0x1xn-1 pro vstup x0x1xn.
S0 je počáteční stav.