Samopal Moore

Moorův automat ( abstraktní automat druhého druhu ) v teorii počítání je konečný automat , jehož výstupní hodnota signálu závisí pouze na aktuálním stavu tohoto automatu a nezávisí přímo, na rozdíl od automatu Mealyho , na vstupní hodnoty. Automat Moore je pojmenován po Edwardu F. Mooreovi , který popsal jeho vlastnosti a publikoval výzkum v roce 1956 v publikaci „Gedanken-experiments on Sequential Machines“ [1] .

Formální definice

Automat Moore lze definovat jako n-tici 6 prvků včetně:

• množina vnitřních stavů S (vnitřní abeceda);
• počáteční stav s 0 ;
• sada vstupních signálů X (vstupní abeceda);
• sada výstupních signálů Y (výstupní abeceda)
• přechodová funkce .
• výstupní funkce .

Komunikace s Mealy Machines

Pro každý Mooreův automat existuje ekvivalentní Mealyho automat : každý Moorův automat lze přeměnit na Mealyho automat přidáním řady vnitřních stavů. Opak, přísně vzato, není pravda: faktem je, že výstupní signál Moorova stroje závisí pouze na vstupním signálu v předchozích časech, zatímco výstupní signál u Mealyho stroje může záviset na vstupním signálu v aktuálním čase. studna. Pro Mealyho automat je v obecném případě možné sestrojit pouze Mooreův automat, který je mu téměř ekvivalentní: totiž jeho výstup bude posunut v čase o 1 [2] . Pokud změníme definici Moorova automatu tak, že automat vypíše hodnotu na konci transakce místo na začátku, pak budou takové automaty zcela ekvivalentní automatům Mealy.

Metody hledání

• Diagram  je orientovaný graf zobrazený na rovině , jehož vrcholy jedna ku jedné odpovídají stavům automatu a oblouky odpovídají vstupním symbolům.
• Tabulka přechodů-výstupů , v jejíchž buňkách jsou pro každou dvojici hodnot argumentů x(t) , s(t) připojeny budoucí vnitřní stavy s(t+1) . Hodnoty výstupního signálu y(t) jsou uvedeny v samostatném sloupci.

Tabulka skoků

	y 1	y2 _	y 3	y 1	y2 _	y2 _	y 3
	s 1	s2 _	s3 _	s4 _	s5 _	s6 _	s7 _
	s5 _	s4 _	s5 _	s3 _	s4 _	s2 _	s5 _
	s7 _	s 1	s4 _	s2 _	s 1	s3 _	s4 _

Viz také

• Simulátor multiplatformního automatu JFLAP , Turingovy stroje, gramatika, kreslení grafů automatů
• Stroj Moore versus stroj Mealy

Poznámky

1. ↑ Moore, Edward F. Gedanken-experiments on sekvenční stroje  //  Automata Studies, Annals of Mathematical Studies. - Princeton, NJ: Princeton University Press, 1956. - Ne. 34 . - S. 129-153 .
2. ↑ Edward A. Lee a Sanjit A. Seshia. Úvod do vestavěných  systémů . - Druhé vydání. - MIT Press , 2017. - S. 58. - ISBN 978-0-262-53381-2 .

Literatura

• Karacuba AA Experimente mit Automaten (německy) // Elektron. Inform.-sloveso. Kybernetik, 11, 611-612 (1975).  (Němec)
• Karatsuba A. A.  Řešení úlohy z teorie konečných automatů // Uspekhi Mat. Nauk, vol. 15, č. 3(93), str. 157-159 (1960).  (Ruština)
• Karatsuba A. A. Seznam vědeckých prací  (v ruštině)
• Karacuba AA Experimente mit Automaten (německy) Elektron. informační slovo. Kybernetik, 11, 611–612 (1975).  (Angličtina)
• Moore EF Gedanken-experimenty na sekvenčních strojích. Automata Studies, Annals of Mathematical Studies, 34, 129–153. Princeton University Press, Princeton, NJ (1956).  (Angličtina)