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: . Non:
 : Egoeren multzo finitua.
 : Hasierako egoera.
 : Sarrerako alfabetoa izeneko multzo finitua.
 : Irteerako alfabetoa izeneko multzo finitua.
 : Trantsizio funtzioa, egoera bat eta sarrera datu bat emanez, hurrengo egoera ematen duena.
 : Irteerako datuen funtzioa, egoera bakoitzaren araberako irteera datuak ematen dituena

 Irudikapena 
++Uneko
egoeraHurrengo
egoeraIrteeraabthumb|405x405px|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  egoera,  sarrera-sinbolo eta  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:  motako Moore makina izanda, egoera bakoitza besteengandik bereizgarria izanik, orduan makinaren amaierako egoera zehazteko erabili daitekeen  luzera maximoko esperimentu adarkatua existitzen da.B Teorema:  motako Moore makina izanda, egoera bakoitza besteengandik bereizgarri izanik, makinaren amaierako egoera zehazten duten esperimentu motzenen luzera  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,  eta  egoerek trantsizio berdinak dituzte sarrera guztietarako. Berdina gertatzen da  eta  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 makinarendiagramaMoore makinarentrantsizio-taulaMealy makinarentrantsizio-taulaSinplifikatutakoMealy makinarentrantsizio-taulaLortutako Mealymakinaren diagramaframeless|300x300pxUneko
egoeraHurrengo
egoeraIrteeraabUneko
egoeraHurrengo
egoeraabUneko
egoeraHurrengo
egoeraab267x267px

 Mealy makinatik, Moore makinara 

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

Orain,  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  motako trantsiziorik), ezin dugu jakin zein den egoeraren irteera, baina irteera hori ez denez inoiz sortuko, edozer jarri daiteke. Adibide hauetan,  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.

Mealymakinaren diagramaMealy makinarentrantsizio-taulaEgokitutakoMealy makinarentrantsizio-taulaMoore makinarentrantsizio-taulaLortutako Moore makinarendiagrama267x267pxUneko
egoeraHurrengo
egoeraabUneko
egoeraHurrengo
egoeraabUneko
egoeraHurrengo
egoeraIrteeraabframeless|300x300px

 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.

 Erreferentziak 

 Ikus, gainera 
 Automata finitu
 Mealy makina
 Kanpo estekak 

Kategoria:Automaten teoria