Moore maskinpistol
Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 31. oktober 2021; verifikation kræver 1 redigering .Moores automat ( abstrakt automat af anden art ) i beregningsteorien er en finit automat , hvor outputværdien af signalet kun afhænger af den aktuelle tilstand af denne automat, og ikke direkte, i modsætning til Mealy automaten , afhænger af. input værdier. Moore-automaten er opkaldt efter Edward F. Moore , som beskrev dens egenskaber og offentliggjorde forskning i 1956 i publikationen "Gedanken-experiments on Sequential Machines" [1] .
Formel definition
En Moore-automat kan defineres som en tuple af 6 elementer, herunder:
- sæt af interne tilstande S (internt alfabet);
- begyndelsestilstand s 0 ;
- sæt af inputsignaler X (input alfabet);
- sæt af udgangssignaler Y (output alfabet)
- overgangsfunktion .
- output funktion .
Kommunikation med Mealy Machines
For enhver Moore-automat er der en tilsvarende Mealy-automat : enhver Moore-automat kan transformeres til en Mealy-automat ved at tilføje et antal interne tilstande. Det omvendte er strengt taget ikke sandt: Faktum er, at udgangssignalet fra Moore-maskinen kun afhænger af inputsignalet på tidligere tidspunkter, mens udgangssignalet for Mealy-maskinen kan afhænge af inputsignalet på det aktuelle tidspunkt som godt. For en Mealy-automat er det i det generelle tilfælde muligt kun at konstruere en Moore-automat, som næsten svarer til den: dens output vil nemlig blive forskudt i tid med 1 [2] . Hvis vi ændrer definitionen af en Moore-automat, så automaten udsender en værdi i slutningen af en transaktion i stedet for i begyndelsen, så vil en sådan automat være fuldstændig ækvivalent med Mealy-automater.
Quest metoder
- Et diagram er en rettet graf afbildet på et plan , hvis toppunkter en-til-en svarer til automatens tilstande, og buerne svarer til inputsymbolerne.
- Tabel over overgange-output , i hvis celler for hvert par af værdier af argumenterne x(t) , s(t ) er anbragt fremtidige interne tilstande s(t+1) . Outputsignalværdier y(t) præsenteres i en separat kolonne.
Spring tabel
| 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 _ |
Se også
- JFLAP cross-platform automat simulator, Turing maskiner, grammatik, automat graftegning
- Moore-maskine versus Mealy-maskine
Noter
- ↑ Moore, Edward F. Gedanken-eksperimenter på sekventielle maskiner // Automata Studies, Annals of Mathematical Studies. - Princeton, NJ: Princeton University Press, 1956. - Nej. 34 . - S. 129-153 .
- ↑ Edward A. Lee og Sanjit A. Seshia. Introduktion til indlejrede systemer . - Anden version. - MIT Press , 2017. - S. 58. - ISBN 978-0-262-53381-2 .
Litteratur
- Karacuba AA Experimente mit Automaten (tysk) // Elektron. Oplys.-udsagnsord. Kybernetik, 11, 611-612 (1975). (Tysk)
- Karatsuba A. A. Løsning af et problem fra teorien om finite automata // Uspekhi Mat. Nauk, bind 15, nr. 3(93), s. 157-159 (1960). (Russisk)
- Karatsuba A. A. Liste over videnskabelige artikler (russisk)
- Karacuba AA Experimente mit Automaten (tysk) Elektron. informationsverarb. Kybernetik, 11, 611-612 (1975). (Engelsk)
- Moore EF Gedanken-eksperimenter på sekventielle maskiner. Automata Studies, Annals of Mathematical Studies, 34, 129–153. Princeton University Press, Princeton, NJ (1956). (Engelsk)