Automat Mealy’ego

Ten artykuł od 2013-09 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła, najlepiej w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Automat Mealy’ego

Automat Mealy’ego – automat, którego wyjście jest funkcją stanu wewnętrznego i sygnałów wejściowych (por. automat Moore’a).

Definicja formalna

Automat Mealy’ego jest to rodzaj deterministycznego automatu skończonego, reprezentowany przez uporządkowaną szóstkę:

${\displaystyle \langle Z,Q,Y,\Phi ,\Psi ,q_{0}\rangle ,}$

gdzie:

• ${\displaystyle Z=\{z_{1},z_{2},\dots ,z_{n}\}}$ – zbiór sygnałów wejściowych,
• ${\displaystyle Q=\{q_{1},q_{2},\dots ,q_{n}\}}$ – zbiór stanów wewnętrznych,
• ${\displaystyle Y=\{y_{1},y_{2},\dots ,y_{n})}$ – zbiór sygnałów wyjściowych,
• ${\displaystyle \Phi }$ – funkcja przejść, ${\displaystyle q(t+1)=\Phi [q(t),z(t)],}$
• ${\displaystyle \Psi }$ – funkcja wyjść, ${\displaystyle y(t)=\Psi [q(t),z(t)],}$ zależy od stanu, w którym znajduje się automat oraz od sygnału wejściowego,
• ${\displaystyle q_{0}}$ – stan początkowy, należy do zbioru Q.

Automat Mealy’ego przedstawia się jako graf skierowany z wyróżnionym wierzchołkiem zwanym stanem początkowym. Podając sygnały na wejście automatu powodujemy zmianę bieżącego stanu i zwrócenie wartości przypisanej do podanego sygnału wejściowego.

Tłumacząc to w sposób bardziej przystępny: Stan wyjść Y automatu Mealy’ego^[1] zależy od stanu wewnętrznego automatu Q (stanu przerzutników / rejestrów) tak jak ma to miejsce w automacie Moore’a, ale również od stanu wejść Z. W diagramie stanów zobrazowane jest to poprzez napis (Z / Y) obok strzałek zmiany stanu (funkcji przejść Φ), czyli dla każdego stanu wejścia Z podawany jest również stan wyjścia Y. W automacie Moore’a podawany jest tylko stan wejścia Z (zob. automat Moore’a). W konsekwencji liczba stanów wewnętrznych Q automatu Mealy’ego może być mniejsza (ten sam stan Q może wystąpić dla różnych stanów wyjść Y) w porównaniu z automatem Moore’a. Okupione to jest z reguły bardziej skomplikowaną logiką Ψ sterującą stanami wyjścia Y oraz większymi czasami propagacji. Podsumowując, wybór pomiędzy automatem Mealy’ego i Moore’a zależy od konkretnego automatu i wymagań.

Przypisy