Moore makina

Informatika konputazionalean, automaten teorian hain zuzen, Moore makina edo Moore automata (Edward F. Moore-k proposatua), automata finitu bat da (transduktore finitu bat hain zuzen), non une zehatz bateko irteera datua soilik uneko egoeraren menpekoa den eta hurrengo egoerarako mugimendua uneko egoeraren eta sarrerako datuen menpe dagoen. Horrek esan nahi du automataren sarrerako sinbolo bakoitzerako irteera sinbolo bat dagoela.

Mealy makinak automata hauen antzekoak dira. Izan ere, biak automata finituen bariazioak dira, non irteerak sortzen diren. Bien arteko desberdintasuna Mealy makinetan irteera datu bakoitza uneko egoeraren eta sarrera datuen menpekoa dela da. Moore makina bakoitzerako Mealy baliokidea existitzen da, eta alderantziz.

Bi eredu hauek baliokideak dira (hau da, funtzio berak errepresentatzeko gai dira), nahiz eta orokorrean Moore makinek egoera gehiago behar dituzten.

Moore makinetan, egoera batek lotuta duen datua egoera horretara iristean sortzen da. Honek aurretik esandakoarekin (sarrerako sinbolo bakoitzeko, irteera sinbolo bat dagoela) kontraesan bat dela iruditu daiteke. Izan ere, sarrerako sinbolorik gabe, hasierako egoeran hasten garenez, hasierako egoeraren irteera sinbolo sortuko dela pentsatu daiteke. Baina hasierako egoera berezia da, Moore makinak ez direlako hasierako egoerara iristen, aldiz, egoera horretan hasten dira zuzenean, eta hortik aurrerako egoera aldaketak dira trantsizioak sortzen dituztenak, aurretik aipatutakoa betez.

Historia

Moore makinen izena Edward F. Moore irakasle estatubatuarraren ohorean ezarri zen, bera izan baitzen hauen asmatzailea. Kontzeptua 1956. urtean argitaratutako “Gedanken-experiments on Sequential Machines” artikuluan agertu zen lehenengo aldiz. 1957. urtean, A. A Karatsubak (Moskuko mekanika eta matematikako fakultateko ikaslea), Moore-ren artikuluan aipatutako bi teoremen frogapena gauzatu zuen, eta 8. teoremaren esperimentuaren mugak hedatu zituen. Frogapen hauek, “Automata finituen teoriako problema bati soluzioa” (ingelesez, Solution to a problem in the theory of finite automatons) izeneko artikuluan idatzi zuen, 1960ko ekainean Uspekhi Matematicheskikh Nauk aldizkarian argitaratu zena.

Definizio formala

Moore makina bat 6-kote batez defini daiteke: $(S,S_{0},\Sigma ,\Lambda ,T,G)$. Non:

• $S$: Egoeren multzo finitua.
• $S_{0}\in S$: Hasierako egoera.
• $\Sigma$: Sarrerako alfabetoa izeneko multzo finitua.
• $\Lambda$: Irteerako alfabetoa izeneko multzo finitua.
• $T:S\times \Sigma \to S$: Trantsizio funtzioa, egoera bat eta sarrera datu bat emanez, hurrengo egoera ematen duena.
• $G:S\to \Lambda$: Irteerako datuen funtzioa, egoera bakoitzaren araberako irteera datuak ematen dituena

Irudikapena

Uneko egoera Hurrengo egoera Irteera a b $\to q_{0}$ $q_{10}$ $q_{20}$ $\lambda$ $q_{10}$ $q_{11}$ $q_{20}$ $0$ $q_{11}$ $q_{11}$ $q_{20}$ $1$ $q_{20}$ $q_{10}$ $q_{21}$ $0$ $q_{21}$ $q_{10}$ $q_{21}$ $1$

Moore Makina baten diagrama. 1 idazten du irteeran, sarreran aa edo bb segidak aurkitzen diren bakoitzean.

Trantsizio-taula baten bidez edo diagrama baten bidez irudikatu daitezke automata finituak.

Trantsizio-taula

Automaten teorian eta logika sekuentzialean, egoeren trantsizio-taula, sarrera datuen eta uneko egoeraren arabera hurrengo egoera zein izango den erakusten duen taula da. Moore makinetan, taula honek egoera bakoitzak sortuko duen irteera ere erakusten du.

Diagrama

Moore makinen diagramak trantsizio-taulak modu grafikoan errepresentatzen dituen diagrama da. Orokorrean, automata finituen diagrama bera erabiltzen da, non egoera bakoitzak sortzen duen irteera erakusten den. Automatak modu argiagoan erakusteko erabiltzen dira, trantsizio-taulak irakurtzea baino argiagoa delako.

Gedanken-experiments on Sequential Machines

Esperimendu teorikoak (Alemanieraz: Gedankenexperiment, Gedanken-Experiment edo Gedankenerfahrung) hipotesi, teoria edo printzipio batzuk abiapuntu bezala izanik, esperimentu batek izan ditzakeen ondorioak frogatzean datza. Esperimentuaren egitura izanik, praktikara eramaterik posible ez den egoerara iritsi gaitezke.

Edward F. Moore-k idatzitako "Gedanken-experiments on Sequential Machines" artikuluan, (n;m;p) motako S automatak (edo makinak, orain Moore makina bezala ezagutzen direnak) definitu zituen. Automatak ${\textbf {n}}$ egoera, ${\textstyle {\textbf {m}}}$ sarrera-sinbolo eta ${\textstyle {\textbf {p}}}$ irteera-sinboloz osatuta daude.

"Kontuan hartutako automatak, egoera kopurua eta sarrera eta irteerako sinbolo posibleen kopurua finitua da. Gainera, makina hauen portaera guztiz determinista da (hau da, ez dira ausazko elementuak onartzen), izan ere, makinaren uneko egoera soilik aurreko sarrera-datuaren eta aurreko egoeraren menpekoa da, eta uneko irteera soilik uneko egoeraren menpekoa da.”

Moore makinaren egiturari buruzko 9 teoremen frogapena eta zenbait esperimentu biltzen dira artikuluan.

A.A Karatsuba-k ondorengo bi teoremen frogapena gauzatu zuen 1957. urtean, 8. teoremaren limitearen hedapena zabalduz. Bi teorema horiek Karatsubak idatzitako “Automata teoriaren arazoa” izeneko artikuluan erabili ziren.

A Teorema: ${\textstyle (m;n;p)}$ motako Moore makina izanda, egoera bakoitza besteengandik bereizgarria izanik, orduan makinaren amaierako egoera zehazteko erabili daitekeen ${\textstyle {\frac {(n-1)(n-2)}{2}}+1}$ luzera maximoko esperimentu adarkatua existitzen da.

B Teorema: ${\textstyle (m;n;p)}$ motako Moore makina izanda, egoera bakoitza besteengandik bereizgarri izanik, makinaren amaierako egoera zehazten duten esperimentu motzenen luzera ${\textstyle {\frac {(n-1)(n-2)}{2}}+1}$ da.

Mealy eta Moore makinen alderaketa

Bai Mealy makinak, bai Moore makinak, mota bi borietatako makinak automata finituak dira, ez dute amaierako egoerarik eta sarrera-datu bakoitzerako irteera-datu bat itzuliko dute.

Mealy makinaren baliokide den Moore makinak egoera kopuru bera edo gehiago izango ditu.

Moore makinetan irteera-datuak egoera bakoitzaren menpe daude. Mealy makinetan, ordea, egoeraren eta sarrerako datuaren (hau da, trantsizioaren) menpe.

Mealy makinetan irteera-datuak erloju-ziklo amaieran gauzatzen dira, Moore makinetan, logika gauzatu eta gero, edonoiz gauzatu daitezke.

Moore eta Mealy makinen arteko bihurketa

Aurretik esan bezala, Moore eta Mealy makinak eredu baliokideak dira. Hortaz, bien arteko bihurketa gauzatu daiteke, ondorengo bi ataletan erakusten den moduan.

Moore makinatik, Mealy makinara

Moore makina bat Mealy makina batera bihurtzea nahiko erraza da. Trantsizio bakoitzaren irteera, horren helburu-egoeraren irteera izango da.

Hau egitean, egoera erredundanteak sortu daitezke. Azpiko adibidean ikusi daitekeen moduan, $q_{10}$ eta $q_{11}$ egoerek trantsizio berdinak dituzte sarrera guztietarako. Berdina gertatzen da $q_{20}$ eta $q_{21}$ egoerekin. Behin egoera bikoiztuak identifikatuta, berdinak diren guztiak egoera bakar batekin ordezkatu ditzakegu. Horrela Moore makinaren guztiz baliokide den Mealy makina sinplifikatu bat lortuko dugu.

Moore makinaren diagrama		Moore makinaren trantsizio-taula		Mealy makinaren trantsizio-taula		Sinplifikatutako Mealy makinaren trantsizio-taula		Lortutako Mealy makinaren diagrama
	$\Longrightarrow$	Uneko egoera Hurrengo egoera Irteera a b $\to q_{0}$ $q_{10}$ $q_{20}$ $\lambda$ $q_{10}$ $q_{11}$ $q_{20}$ $0$ $q_{11}$ $q_{11}$ $q_{20}$ $1$ $q_{20}$ $q_{10}$ $q_{21}$ $0$ $q_{21}$ $q_{10}$ $q_{21}$ $1$	$\Longrightarrow$	Uneko egoera Hurrengo egoera a b $\to q_{0}$ $(q_{10},0)$ $(q_{20},0)$ $q_{10}$ $(q_{11},1)$ $(q_{20},0)$ $q_{11}$ $(q_{11},1)$ $(q_{20},0)$ $q_{20}$ $(q_{10},0)$ $(q_{21},1)$ $q_{21}$ $(q_{10},0)$ $(q_{21},1)$	$\Longrightarrow$	Uneko egoera Hurrengo egoera a b $\to q_{0}$ $(q_{1},0)$ $(q_{2},0)$ $q_{1}$ $(q_{1},1)$ $(q_{2},0)$ $q_{2}$ $(q_{1},0)$ $(q_{2},1)$	$\Longrightarrow$

Mealy makinatik, Moore makinara

Bihurketa hau aurrekoaren kontrakoa denez, egoera berriak sortu behar izan daitezke. Formalki, Moore makinaren $q_{i}$ egoeraren irteera $\alpha$ izango da, Mealy makinan $q_{i}$ egoerara doazen trantsizio guztiek $(q_{i},\alpha )$ itxura badute. Hortaz, arazo bat sortzen da $q_{i}$ egoerara doazen trantsizioek irteera desberdinak sortzen dituztenean. Kasu horretan $q_{i\alpha }$ egoera berriak sortuko dira, $\displaystyle (q_{i},\alpha )$ motako egoera desberdin bakoitzeko.

Orain, $q_{i}$ egoera guztietara doazen trantsizioak irteera berdina sortzen dutenez, trantsizio horien irteera haien helburu-egoerari esleitu besterik ez da egin behar.

Azkenik, hasierako egoerara trantsiziorik ez badago (hau da, ez badago $(q_{0},\alpha )$ motako trantsiziorik), ezin dugu jakin zein den $q_{0}$egoeraren irteera, baina irteera hori ez denez inoiz sortuko, edozer jarri daiteke. Adibide hauetan, $\lambda$ erabili da edozein irteera errepresentatzeko. Hasierako egoera ez den beste batera trantsiziorik ez balego, egoera hori guztiz erredundantea da (ezin delako egoera horretara iritsi), eta hortaz ezabatu daiteke.

Mealy makinaren diagrama		Mealy makinaren trantsizio-taula		Egokitutako Mealy makinaren trantsizio-taula		Moore makinaren trantsizio-taula		Lortutako Moore makinaren diagrama
	$\Longrightarrow$	Uneko egoera Hurrengo egoera a b $\to q_{0}$ $(q_{1},\color {red}0\color {black})$ $(q_{2},\color {red}0\color {black})$ $q_{1}$ $(q_{1},\color {red}1\color {black})$ $(q_{2},\color {red}0\color {black})$ $q_{2}$ $(q_{1},\color {red}0\color {black})$ $(q_{2},\color {red}1\color {black})$	$\Longrightarrow$	Uneko egoera Hurrengo egoera a b $\to q_{0}$ $(q_{10},0)$ $(q_{20},0)$ $q_{10}$ $(q_{11},1)$ $(q_{20},0)$ $q_{11}$ $(q_{11},1)$ $(q_{20},0)$ $q_{20}$ $(q_{10},0)$ $(q_{21},1)$ $q_{21}$ $(q_{10},0)$ $(q_{21},1)$	$\Longrightarrow$	Uneko egoera Hurrengo egoera Irteera a b $\to q_{0}$ $q_{10}$ $q_{20}$ $\lambda$ $q_{10}$ $q_{11}$ $q_{20}$ $0$ $q_{11}$ $q_{11}$ $q_{20}$ $1$ $q_{20}$ $q_{10}$ $q_{21}$ $0$ $q_{21}$ $q_{10}$ $q_{21}$ $1$	$\Longrightarrow$

Aplikazioak

Edozein automata finituk hainbat aplikazio izan ditzake, hala nola:

• Konpiladoreetan eta analizatzaile lexikaletan, adierazpen erregularrekin patroiak identifikatzeko erabiltzen dira. Gainera, Moore makinek irteera bat sor dezaketenez, token mota bakoitzerako identifikatzaile desberdin bat eman dezake.
• Sistema sekuentzial sinkronoak murriztapenak dituzten Moore makinak bezala errepresentatu daitezke, non uneko egoera erloju-ziklo bakoitzean aldatzen den. Zirkuitu elektronikoetan, egoera flip-flopetan gordetzen da eta erlojuaren seinale global hauek gordetzen duten balioa aldatzea ahalbidetzen du. Mealy makinek sarrerekiko azkarrago funtzionatzen dute. Orokorrean erloju-ziklo berean erreakzionatzen dute. Moore makinetan logika gehiago behar da irteerak dekodifikatzeko, atzerapen handiagoa sortuz.

   Elektronika aplikatuan, zirkuitu sekuentzial guztiak ezin dira Mealy makinen bidez inplementatu, batzuk soilik Moore makinekin inplementatu daitezke.

Ikus, gainera

• Automata finitu
• Mealy makina

Kanpo estekak

Horton., Conway, John. (). Regular algebra and finite machines,. Chapman and Hall ISBN 0412106205. PMC 281194..

• Datuak: Q640119
• Multimedia: Moore machine / Q640119