Mooren konepistooli

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 31. lokakuuta 2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Mooren automaatti ( toisen tyyppinen abstrakti automaatti ) on laskentateoriassa äärellinen automaatti , jonka signaalin lähtöarvo riippuu vain tämän automaatin nykyisestä tilasta, eikä se ole suoraan riippuvainen, toisin kuin Mealy-automaatti . syöttöarvot. Moore-automaatti on nimetty Edward F. Mooren mukaan, joka kuvaili sen ominaisuuksia ja julkaisi tutkimuksen vuonna 1956 julkaisussa "Gedanken-experiments on Sequential Machines" [1] .

Muodollinen määritelmä

Moore-automaatti voidaan määritellä 6 elementin monikkona, mukaan lukien:

joukko sisäisiä tiloja S (sisäinen aakkoset);
alkutila s 0 ;
joukko tulosignaaleja X (tuloaakkoset);
lähtösignaalien joukko Y (lähtöaakkoset)
siirtymätoiminto . $\Phi :S\times X\rightarrow S$
lähtötoiminto . $\operaattorinimi {G} :S\rightarrow Y$

Viestintä Mealy Machinesin kanssa

Jokaiselle Moore-automaatille on olemassa vastaava Mealy-automaatti : mikä tahansa Moore-automaatti voidaan muuntaa Mealy-automaatiksi lisäämällä joukko sisäisiä tiloja. Tarkkaan ottaen päinvastoin ei pidä paikkaansa: tosiasia on, että Mooren koneen lähtösignaali riippuu vain tulosignaalista aikaisempina aikoina, kun taas Mealy-koneen lähtösignaali voi riippua tulosignaalista kulloinkin . hyvin. Mealy-automaatille on yleensä mahdollista rakentaa vain Moore-automaatti, joka on lähes samanlainen kuin se: eli sen lähtöä siirretään ajallisesti 1 [2] . Jos muutamme Mooren automaatin määritelmää niin, että automaatti tulostaa arvon tapahtuman lopussa eikä sen alussa, niin tällaiset automaatit vastaavat täysin Mealyn automaatteja. ${\näyttötyyli \operaattorin nimi {G} (s)}$ $s\rightarrow s'$

Tehtävämenetelmät

Kaavio on tasolle kuvattu suunnattu graafi , jonka kärjet yksi yhteen vastaavat automaatin tiloja ja kaaret vastaavat syötesymboleja.
Siirtymien-ulostulojen taulukko , jonka soluihin jokaiselle argumenttien x(t) , s(t) arvoparille on liitetty tulevat sisäiset tilat s(t+1) . Lähtösignaalin arvot y(t) esitetään erillisessä sarakkeessa.

Hyppypöytä

	v 1	y2_ _	v 3	v 1	y2_ _	y2_ _	v 3
	s 1	s2_ _	s3_ _	s4_ _	s5_ _	s6_ _	s7_ _
$x_{1}$	s5_ _	s4_ _	s5_ _	s3_ _	s4_ _	s2_ _	s5_ _
$x_{2}$	s7_ _	s 1	s4_ _	s2_ _	s 1	s3_ _	s4_ _

Katso myös

JFLAP cross-platform automaattinen simulaattori, Turingin koneet, kielioppi, automaatiograafin piirtäminen
Moore kone vs. Mealy kone

Muistiinpanot

↑ Moore, Edward F. Gedanken-kokeet peräkkäisillä koneilla // Automata Studies, Annals of Mathematical Studies. - Princeton, NJ: Princeton University Press, 1956. - Ei. 34 . - s. 129-153 .
↑ Edward A. Lee ja Sanjit A. Seshia. Johdatus sulautettuihin järjestelmiin . - Toinen painos. - MIT Press , 2017. - s. 58. - ISBN 978-0-262-53381-2 .

Kirjallisuus

Karacuba AA Experimente mit Automaten (saksa) // Elektron. Inform.-verarb. Kybernetik, 11, 611 - 612 (1975). (Saksan kieli)
Karatsuba A. A. Ongelman ratkaisu äärellisten automaattien teoriasta // Uspekhi Mat. Nauk, osa 15, nro 3(93), s. 157 - 159 (1960). (Venäjän kieli)
Karatsuba A. A. Luettelo tieteellisistä kirjoituksista (venäläinen)
Karacuba AA Experimente mit Automaten (saksa) Elektron. informationsverarb. Kybernetik, 11, 611–612 (1975). (Englanti)
Moore EF Gedanken -kokeet peräkkäisillä koneilla. Automata Studies, Annals of Mathematical Studies, 34, 129–153. Princeton University Press, Princeton, NJ (1956). (Englanti)