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.
q₀ ye l stado enicial, esto ye, l stado de l'outómato antes de qualquiera antrada ser processada, adonde q₀ ∈ 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 la₁,la₂,...., la_m, adonde la_i ∈ Σ, 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 = la₁,la₂,...., la_m ∈ Σ*, ye ua sequéncia de stados q₁,q₂,...., q_m, adonde q_i ∈ Q tal que q₀ ye l stado enicial i q_i = δ(q_i-1,la_i) para 0 < i ≤ m. An outras palabras, ne l'ampeço l'outómato stá ne l stado enicial q₀, 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 q_i = δ(q_i-1,la_i). 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 q_m ∈ 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.^[1]

Conexon cula teorie de las catadories

Puode-se defenir muitas catadories defrentes d'outómatos^[2] 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,^[3]^[4] que ten ambos, co-lemites i lemites categóricos. Un homomorfismo d'outómato mapeia ua 5-tupla dun outómato La_i nua 5-tupla d'outro outómato La_j.^[5] 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 S_g. Monoides son tamien cunsidrados cumo un ambiente propício para outómatos an catadories monoides.^[6]^[7]^[8]

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 La_i-->La_i. 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óides^[9] ó 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).

↑ 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^{[lhigaçon einatiba]}
↑ Jirí Adámek and Bera Trnkobá. 1990. Outomata and Algebras in Categories. Kluwer Academic Publishers:Dordrecht and Prague
↑ S. Mac Lane, Categories fur the Working Mathematician, Springer, New York (1971)
↑ http://planetmath.org/ancyclopedie/CartesianClosedCategory.html^{[lhigaçon einatiba]} Cartesian closed category
↑ http://planetmath.org/ancyclopedie/SequentialMachine3.html^{[lhigaçon einatiba]} The Category of Outomata
↑ http://www.cse.wbu.edu/~jworthing/asl2010.pdf^{[lhigaçon einatiba]} James Worthington.2010.Determenizing, Forgetting, and Outomata in Monoidal Categories. ASL North Amarican Annual Meting,March 17, 2010
↑ Aguiar, 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
↑ http://en.wikipedie.org/wiki/Groupoid#Category_of_groupoids Category of groupoids

Antrodution to Outomata Theory, Languages, and Cumputation (2nd Eidition). [S.l.]: Pearson Eiducation. 2000. ISBN 0-201-44124-1
Antrodution to the Theory of Cumputation. [S.l.]: PWS Publishing. 1997. ISBN 0-534-94728-X 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.
Porducing a top-down parse ourder with botton-up parsing. [S.l.]: Eilsebier North-Holland. 1995

Teoria de autômatos: linguagem formal e gramática formal
Hierarquia Chomsky	Gramática	Linguagem	Reconhecedor
Tipo-0	Irrestrita	Recursivamente enumerável	Máquina de Turing
--	--	Recursiva	Máquina de Turing que sempre para
Tipo-1	Sensível ao contexto	Sensível ao contexto	Autômato linearmente limitado
Tipo-2	Livre de contexto	Livre de contexto	Autômato com pilha
Tipo-3	Regular	Regular	Autômato finito

Softwares

SCTMF - Software para Criaçon i Teste de Modelos Formales.
JFlap - Software amaricano para testes cun anterface gráfica.
.com/auger/ Auger - Ambiente para custruçon i simulaçon d'outómatos fenitos.
.com Simulador de Outomatos - L Simulador de Outómatos ye ua ferramienta pa la criaçon, simulaçon i cumberson de modelos formales, zambolbida cul oubjetibo d'auxeliar l daprendizado de Lenguaiges Formales i Outómatos.

[1] 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^{[lhigaçon einatiba]}

[2] Jirí Adámek and Bera Trnkobá. 1990. Outomata and Algebras in Categories. Kluwer Academic Publishers:Dordrecht and Prague

[3] S. Mac Lane, Categories fur the Working Mathematician, Springer, New York (1971)

[4] ttp://planetmath.org/ancyclopedie/CartesianClosedCategory.html^{[lhigaçon einatiba]} Cartesian closed category

[5] ttp://planetmath.org/ancyclopedie/SequentialMachine3.html^{[lhigaçon einatiba]} The Category of Outomata

[6] ttp://www.cse.wbu.edu/~jworthing/asl2010.pdf^{[lhigaçon einatiba]} James Worthington.2010.Determenizing, Forgetting, and Outomata in Monoidal Categories. ASL North Amarican Annual Meting,March 17, 2010

[7] Aguiar, M. and Mahajan, S.2010. "Monoidal Funtors, Species, and Hopf Algebras".

[8] Meseguer, J., Montanari, U.: 1990 Petri nets are monoids. Anformation and Cumputation 88:105–155

[9] ttp://en.wikipedie.org/wiki/Groupoid#Category_of_groupoids Category of groupoids

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]