Teorie de ls outómatos

Na Ciéncia de la cumputaçon teórica, teorie de ls outómatos ye l studo de ls oubjetos matemáticos chamados máquinas abstratas ó outómatos i ls porblemas cumputacionales que puoden ser resolbidos usando esses oubjetos. Outómato ben de la palabra griega αὐτόματα que senefica “açon sin anfluéncia sterna; outomático”.

La figura al lado eilustra ua máquina de stados fenitos, que pertence a ua bariadade bien coincida d'outómato. Este outómato cunsiste an stados (repersentados na figura por círclos), i trasiçones (repersentado por setas). Quando l'outómato recibe un simblo d'antrada, el faç ua trasiçon (ó salto) para outro stado, d'acuordo cun sue funçon de trasiçon (que ten cumo antradas l stado atual i l simblo recente).

Teorie de ls outómatos tamien stá perfundamente relacionada a la teorie de las lenguaiges formales. Un outómato ye ua repersentaçon fenita dua lenguaige formal que puode ser un cunjunto anfenito. Outómatos son frequentemente classeficados pula classe de las lenguaiges formales que son capazes de recoincer.

Outómatos zampenhan un papel amportante an teorie de la cumputaçon, eilaboraçon de cumpiladores, parsing i berificaçon formal.

Outómatos
Segue ua defeniçon antrodutória dun tipo d'outómatos, qu'ajuda al abordar ls cunceitos eissenciales ambolbidos na teorie de ls outómatos.

Çcriçon Anformal

Un outómato ye suposto para rodar subre ua dada sequéncia de antradas an passos de tiempo çcretos. Para cada passo, un outómato recibe ua antrada que ye oubtida a partir dun cunjunto de simblos ó letras, que ye chamado de alfabeto. An qualquiera momiento, ls simblos que serben d'antrada pa l'outómato forman ua sequéncia fenita de simblos, que ye chamada de palabra. Un outómato cuntén un cunjunto fenito de stados. Para cada anstante de tiempo durante l'eisecuçon, l'outómato stá an un de sous stados. Para cada medida de tiempo an que l'outómato lé un simblo, el pula ó faç la trasiçon para un próssimo stado que ye decidido por ua funçon que ten l'estado atual i l simblo mais recentemente lido cumo parámetros. Esta funçon ye chamada de funçon de trasiçon. L'outómato lé ls simblos de la palabra d'antrada, un simblo por beç, i faç la trasiçon de stado para estado, d'acuordo cula funçon de trasiçon, até la palabra ser totalmente lida. Ua beç que la palabra d'antrada tubir sido lida, l'outómato debe parar i l stado ne l qual l'outómato parou ye chamado de estado final. Dependendo de l stado final, l'outómato puode aceitar ó rejeitar ua palabra d'antrada. Eesiste un subconjunto de stados de l'outómato, que ye defenido cumo l cunjunto de stados d'aceitaçon. Se l stado final ye un estado d'aceitaçon, anton l'outómato aceita la palabra. Causo cuntrairo, la palabra ye rejeitada. L cunjunto de todas las palabras aceitas por un outómato ye chamado de lenguaige reconhecida pul outómato.

Resumindo, un outómato ye un oubjeto matemático que ten ua palabra d'antrada i decide se aceita ó rejeita esta palabra. Cumo todos ls porblemas cumputacionales son redutibles pa l porblema d'aceitaçon de palabras (todas las anstáncias de l porblema puoden ser repersentadas por un tamanho fenito de simblos), la teorie de ls outómatos zampenha un amportante papel na teorie cumputacional.

Defeniçon formal
Outómatos
Un outómato ye repersentado formalmente por ua 5-tupla (Q,Σ,δ,q0,F), adonde:
Q ye un cunjunto fenito de stados.
Σ ye un cunjunto fenito de simblos, chamado de alfabeto de l'outómato.
δ ye la funçon de trasiçon, esto ye, δ: Q x Σ → Q.
q0 ye l stado enicial, esto ye, l stado de l'outómato antes de qualquiera antrada ser processada, adonde q0 ∈ Q.
F ye un cunjunto de stados de Q (esto ye, F ⊆ Q) chamado d'estados d'aceitaçon.

Palabra d'antrada
Un outómato lé ua string fenita de simblos la1,la2,...., lam, adonde lai ∈ Σ, que ye chamada de palabra d'antrada. L cunjunto de todas las palabras ye denotado por Σ*.

Eisecuçon
La eisecuçon dun outómato subre ua palabra d'antrada w = la1,la2,...., lam ∈ Σ*, ye ua sequéncia de stados q1,q2,...., qm, adonde qi ∈ Q tal que q0 ye l stado enicial i qi = δ(qi-1,lai) para 0 < i ≤ m. An outras palabras, ne l'ampeço l'outómato stá ne l stado enicial q0, i anton l'outómato lé simblos de la palabra d'antrada sequencialmente. Quando l'outómato lé l simblo ai el pula pa l stado qi = δ(qi-1,lai). Diç-se que qn ye l stado final de l'eisecuçon.

Palabra d'aceitaçon
Ua palabra w ∈ Σ* ye aceita pul outómato se qm ∈ F.

Lenguaige reconhecida
Un outómato puode recoincer ua lenguaige. La lenguaige L ⊆ Σ* reconhecida por un outómato ye l cunjunto de todas las palabras que son aceitas pul outómato.

Lenguaiges reconhecibles
Las lenguaiges reconhecibles son l cunjunto de lenguaiges que son reconhecidas por algun outómato. Pa la defeniçon arriba d'outómatos, las lenguaiges reconhecibles son lenguaiges regulares. Para defrentes defeniçones d'outómatos, la defeniçon de lenguaiges reconhecibles ye  defrente.

Defeniçones bariantes d'outómatos

Outómatos son defenidos para studar máquinas úteles subre formalismo matemático. Anton, la defeniçon dun outómato ye abierta la bariaçones d'acuordo cula “máquina de l mundo rial”, que nós queremos modelar usando l'outómato. Hai studos de las muitas bariaçones d'outómatos. La percipal bariante, çcrita arriba, ye chamada de outómato fenito determinístico. Seguen bariaçones populares de la defeniçon de ls defrentes cumponentes d'outómatos.

Antrada
Antrada fenita: Un outómato qu'aceita solo sequéncias fenitas de simblos. La defeniçon antrodutória arriba angloba solo palabras fenitas.
Antrada anfenita: Un outómato qu'aceita palabras anfenitas (ω-palabras). Estes outómatos son chamados de ω-outómatos.
Antrada palabra arble: L'antrada puode ser ua arble de simblos al ambés dua sequéncia de simblos. Neste causo, passado ler cada simblo, l'outómato lé todos ls simblos sucessores na arble d'antrada. Diç-se que l'outómato faç ua cópia del mesmo para cada sucessor, i cada cópia eisecuta un simblo sucessor de l stado d'acuordo cula relaçon de trasiçon de l'outómato. Este outómato ye chamado de outómato arble.
Antrada arble anfenita: Las dues stensones arriba puoden ser cumbinadas, anton l'outómato lé ua strutura d'arble cun (in)fenitos zbios. Este outómato ye chamado d'outómato arble anfenita.

Estados
Stados fenitos: Un outómato que cuntén solo un númaro fenito de stados. La defeniçon antrodutória solo çcribe outómatos cun númaros fenitos de stados.
Stados anfenitos: Un outómato que puode nun tener un númaro fenito de stados, ó até mesmo un númaro cuntable de stados. Por eisemplo, l outómato fenito quantun ó outómato topológico ten un númaro anfenito ancontable de stados.
Pilha de mimória: Un outómato puode tamien cunter ua mimória stra ne l formato de pilha, an que simblos puoden ser colocados i retirados.  Este tipo d'outómato ye chamado de outómato pushdown.

Funçon de trasiçon
Determinística: Para un dado stado atual i un simblo d'antrada, se un outómato puode pular para un stado solo anton el ye un outómato determinístico.
Nó-Determenismo: Un outómato que, passado ler un simblo d'antrada, puode pular para qualquiera stado, decidido por sue relaçon de trasiçon. Note que l termo funçon de trasiçon ye sustituído por relaçon de trasiçon: L'outómato nó-determinísticamente decide pular para ua de las oupçones permitidas. Este outómato ye chamado de outómato nó-determinístico.
Altarnamiento: Esta eideia ye mui semelhante al outómato arble, mas ortogonal. L'outómato puode eisecutar sues cópias múltiplas subre l mesmo simblo a ser lido. Este outómato ye chamado de outómato fenito altarnado. La cundiçon d'aceitaçon debe sastifazer todas las eisecuçones de tales cópias para aceitar l'antrada.

Cundiçon d'aceitaçon
Aceitaçon de palabras fenitas: Cumo çcrito na defeniçon anformal arriba.
Aceitaçon de palabras anfenitas: Un ω-outómato nun puode tener stados finales, yá que palabras anfenitas nunca treminan. Preferencialmente, aceitaçon de la palabra ye decidida analisando las sequéncias anfenitas de ls stados bejitados durante l'eisecuçon.
Aceitaçon porbabilística: Un outómato nun percisa stritamente aceitar ó rejeitar ua antrada. El puode aceitar l'antrada cun ua porbabelidade antre zero i un. Por eisemplo, outómato fenito quantun, outómato geométrico i outómato métrico ténen aceitaçon porbabilística.

Defrentes cumbinaçones de las bariaçones arriba porduzen mais classe d'outómato.

Teorie de Outómatos

Teorie d'outómatos ye un assunto que studa las propiadades de bários tipos d'outómatos. Por eisemplo, las questones a seguir son relacionadas a un dado tipo d'outómatos.

Qual classe de lenguaiges formales ye reconhecible por algun tipo d'outómato? (lenguaiges reconhecibles)
Ciertos outómatos son cerrados subre l'ounion, anterseçon ó cumplemiento de lenguaiges formales? (propiadades de fechamiento)
Quon spressibo ye un tipo d'outómato an tenermos de recoincer classe de lenguaiges formales? I, quanto al poder relatibo de spressebidade? (hierarquia de lenguaige)

Teorie de ls outómatos tamien studa se eisiste algun algoritmo efetibo ó nun para resulber porblemas semelhantes a la seguinte lista:

Un outómato aceita algua palabra d'antrada? (berificaçon de bazio – bacuidade)
Ye possible trasformar un dado outómato nó-determinístico nun outómato determinístico sin mudar la lenguaige reconhecible? (determenizaçon)
Para ua dada lenguaige formal, qual ye l menor outómato que la reconhece? (menimizaçon).

Classe de Outómatos

Segue ua lista ancumpleta de tipos d'outómatos.

 Outómatos Lenguaige reconhecible Outómatos fenitos determinísticos(AFD) Lenguaiges regulares Outómatos Finitos Nó-determinísticos(AFN) regular languages Outómatos Finitos Nó-determinísticos cun ε-trasiçones (FND-ε or ε-AFN) Lenguaiges regulares Outómato cun Pilha (AP) Lenguaiges libre de cuntesto Outómato linearmente lemitado (ALL) Lenguaige sensible al cuntesto Máquinas de Turing Lenguaige recursibamente enumerable Outómatos temporizado Outómato de Buchi Lenguaiges ω-lemite Outómatos Nó-determinístico de Buchi Lenguaiges ω-regular Outómatos Nó-determinístico/Determinístico de Rabin Lenguaiges ω-regular Outómatos Nó-determinístico/Determinístico de Stret Lenguaiges ω-regular Outómatos Nó-determinístico/Determinístico de Paridade Lenguaiges ω-regular Outómatos Nó-determinístico/Determinístico de Muller Lenguaiges ω-regular

Outómatos çcretos, cuntinos i híbridos

Giralmente teorie de ls outómatos çcribe ls stados de máquinas abstratas, mas eisisten outómatos analógicos, cuntinos ó híbridos (çcreto-cuntino), que úsan dados analógicos, tiempo cuntino, ó ambos.

Aplicaçones
Cada modelo an teorie de ls outómatos zampenha papéis amportantes an muitas árias aplicadas. Outómatos fenitos son ousados an processamiento de testo, cumpiladores i porjeto d'hardware. Gramáticas libres de cuntesto (GLCs) son ousadas an lenguaiges de porgramaçon i anteligéncia artificial. Ouriginalment, GLCs éran ousadas ne l studo de lenguaiges houmanas. Outómatos telemobles son ousados ne l campo de la biologie, l'eisemplo mais quemun ye l de Jogo de la Bida de John Cunway. Outros eisemplos que podien ser splicados usando teorie de ls outómatos an biologie ancluen crecimiento de pinhas i molusco i padrones de pigmentaçon. Ando mais loinge, ua teorie que sugere que to l'ouniberso ye cumputado por algun tipo d'outómato çcreto ye defendida por cientistas. L'eideia ben de l trabalho de Konrad Zuse, i fui popularizada na América por Edward Fredkin.

Simuladores d'outómatos
Simuladores d'outómatos son ferramientas pedagógicas ousadas para ansinar, daprender i pesquisar teorie de ls outómatos. Un simulador d'outómato ten cumo antrada la çcriçon dun outómato i anton simula sou funcionamiento para ua string arbitrária cumo antrada. La çcriçon de l'outómato puode ser anserida de bárias formas. Un outómato puode ser defenido por ua lenguaige simbólica ó sue specificaçon puode ser anserida nua forma predefenida ó sou diagrama de trasiçon puode ser porjetado ne l clicar i arrastrar de l mouse. Simuladores d'outómatos bien coincidos ancluen Turing’s World, JFLAP, BAS, TAGS i SimStudio.Chakraborty, P., Saxena, P. C., Katti, C. P. 2011. Fifty Years of Outomata Simulation: La Rebiew. ACM Anroads, 2(4):59–70. http://dl.acn.org/citation.cfn?id=2038893&dl=ACM&coll=DL&CFID=65021406&CFTOKEN=86634854

Conexon cula teorie de las catadories
Puode-se defenir muitas catadories defrentes d'outómatosJirí Adámek and Bera Trnkobá. 1990. Outomata and Algebras in Categories. Kluwer Academic Publishers:Dordrecht and Prague seguindo la classeficaçon d'outómatos an defrentes tipos, çcrita na seçon anterior. La catadorie matemática de ls outómatos determinísticos, máquinas sequenciales ó outómatos sequenciales, i máquinas de Turing cun homomorfismos d'outómatos, que define las setas antre outómatos ye ua catadorie cerrada cartesiana,S. Mac Lane, Categories fur the Working Mathematician, Springer, New York (1971)http://planetmath.org/ancyclopedie/CartesianClosedCategory.html Cartesian closed category que ten ambos, co-lemites i lemites categóricos. Un homomorfismo d'outómato mapeia ua 5-tupla dun outómato Lai nua 5-tupla d'outro outómato Laj.http://planetmath.org/ancyclopedie/SequentialMachine3.html The Category of Outomata Homomorfismo d'outómatos tamien puode ser cunsidrado cumo trasformaçones d'outómatos ó homomorfismos semigrupo, quando l spácio de l stado, S, de l'outómato ye defenido cumo un semigrupo Sg. Monoides son tamien cunsidrados cumo un ambiente propício para outómatos an catadories monoides.http://www.cse.wbu.edu/~jworthing/asl2010.pdf James Worthington.2010.Determenizing, Forgetting, and Outomata in Monoidal Categories. ASL North Amarican Annual Meting,March 17, 2010Aguiar, M. and Mahajan, S.2010. "Monoidal Funtors, Species, and Hopf Algebras".Meseguer, J., Montanari, U.: 1990 Petri nets are monoids. Anformation and Cumputation 88:105–155

Catadories d'outómatos bariables
Puode-se tamien defenir un outómato bariable, ne l sentido de Norbert Wiener an sou libro “Houman Use of Houman Beings” puls andomorfismos Lai-->Lai. Anton, puode-se amostrar qu'estes homomorfismos d'outómatos bariables forman un grupo matemático. Ne l causo de l nó-determinístico, ó outros tipos cumplexos d'outómatos, l radadeiro cunjunto d'andomorfismo puode tornar-se, assi i todo, un grupóide de outómato bariable. Antoce, ne l causo mais giral, catadories d'outómatos bariables de qualquiera tipo son catadories de grupóideshttp://en.wikipedie.org/wiki/Groupoid#Category_of_groupoids Category of groupoids ó catadories grupóides. Para alhá desso, la catadorie d'outómatos rebersibles ye anton ua 2-catadorie, i tamien ua subcategoria de a 2-catadorie de grupóides, ó la catadorie grupóide.

 Refréncias 
John I. Hopcroft, Rajeb Motwani, Jeffrey D. Ullman – Antroduçon a la Teorie de Outómatos, Lenguaiges i Cumputaçon (2ª Eidiçon).


  Part One: Outomata and Languages, chaters 1–2, pp. 29–122. Setion 4.1: Decidable Languages, pp. 152–159. Setion 5.1: Undecidable Porblems fron Language Theory, pp. 172–183.


 Softwares 





Catadorie:Teorie de la cumputaçon