Moore kulspruta
Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 31 oktober 2021; verifiering kräver 1 redigering .Moores automat ( abstrakt automat av det andra slaget ) i beräkningsteorin är en finit automat , vars utgångsvärde för signalen endast beror på det aktuella tillståndet för denna automat och inte direkt, till skillnad från Mealy-automaten , beror på ingångsvärden. Moore-automaten är uppkallad efter Edward F. Moore , som beskrev dess egenskaper och publicerade forskning 1956 i publikationen "Gedanken-experiments on Sequential Machines" [1] .
Formell definition
En Moore-automat kan definieras som en tupel av 6 element inklusive:
- uppsättning interna tillstånd S (internt alfabet);
- initialtillstånd s0 ; _
- uppsättning ingångssignaler X (ingångsalfabet);
- uppsättning utsignaler Y (utgångsalfabet)
- övergångsfunktion .
- utgångsfunktion .
Kommunikation med Mealy Machines
För alla Moore-automater finns det en likvärdig Mealy-automat : vilken Moore-automat som helst kan omvandlas till en Mealy-automat genom att lägga till ett antal interna tillstånd. Det omvända, strängt taget, är inte sant: faktum är att utsignalen från Moore-maskinen endast beror på ingångssignalen vid tidigare tidpunkter, medan utsignalen för Mealy-maskinen kan bero på insignalen vid den aktuella tiden som väl. För en Mealy-automat är det i det allmänna fallet möjligt att endast konstruera en Moore-automat, vilket nästan är likvärdigt med den: nämligen dess uteffekt kommer att förskjutas i tiden med 1 [2] . Om vi ändrar definitionen av en Moore-automat så att automaten matar ut ett värde i slutet av en transaktion istället för i början, så kommer en sådan automat att vara helt likvärdig med Mealy-automater.
Quest metoder
- Ett diagram är en riktad graf avbildad på ett plan , vars hörn en-till-en motsvarar automatens tillstånd och bågarna motsvarar ingångssymbolerna.
- Tabell över övergångar-utgångar , i vars celler för varje par av värden av argumenten x(t) , s(t ) är anbringade framtida interna tillstånd s(t+1) . Utsignalvärden y(t) presenteras i en separat kolumn.
Hoppa tabell
| 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 även
- JFLAP plattformsoberoende automatsimulator, Turingmaskiner, grammatik, automatgrafritning
- Moore maskin kontra Mealy maskin
Anteckningar
- ↑ Moore, Edward F. Gedanken-experiment på sekventiella maskiner // Automata Studies, Annals of Mathematical Studies. - Princeton, NJ: Princeton University Press, 1956. - Nej . 34 . - S. 129-153 .
- ↑ Edward A. Lee och Sanjit A. Seshia. Introduktion till inbyggda system . - Andra upplagan. - MIT Press , 2017. - P. 58. - ISBN 978-0-262-53381-2 .
Litteratur
- Karacuba AA Experimente mit Automaten (tyska) // Elektron. Inform.-verb. Kybernetik, 11, 611-612 (1975). (Tysk)
- Karatsuba A. A. Lösning av ett problem från teorin om finita automater // Uspekhi Mat. Nauk, vol. 15, nr 3(93), sid. 157-159 (1960). (ryska)
- Karatsuba A. A. Lista över vetenskapliga artiklar (ryska)
- Karacuba AA Experimente mit Automaten (Tyska) Elektron. informationsverarb. Kybernetik, 11, 611–612 (1975). (Engelsk)
- Moore EF Gedanken-experiment på sekventiella maskiner. Automata Studies, Annals of Mathematical Studies, 34, 129–153. Princeton University Press, Princeton, NJ (1956). (Engelsk)