Outómato

Formalmente, un **outómato** ye defenido cumo sendo un modelo matemático dua máquina d'estados fenitos.

Un **outómato** funciona cumo un reconhecedor dua detreminada lenguaige i sirbe para modelar ua máquina ó, se quejiren, un cumputador simples. Ye ousado, por eisemplo, an eiditores de testo para recoincer padrones. Un cunceito fundamental ne ls outómatos ye l cunceito de stado. Este cunceito ye aplicado la qualquiera sistema, por eisemplo, a la nuossa telebison. Las noçones de stado i sistema son tan onipresentes que fui zambolbido un campo de coincimiento chamado Teorie de ls sistemas. Ua telebison puode star ligada(on) ó çligada(ouff), tenemos anton un sistema cun dous stados.

L'un nible mais detalhado, podemos zeiar defrenciar ls canhales, causo an que podemos tener cientos de stados: un para *çligada* i ls restantes seneficando *ligada ne l canhal N*, eisiste siempre un númaro fenito de stados. Dada ua telebison, eilha nun stá solo nun de ls stados possibles, somos capazes de fazer mudar la telebison de stado.

## Outómatos fenitos
San reconhecedores de lenguaiges regulares defenidos atrabeç de quíntuplas de la forma: 

: ` <math> M=(Q,\  \Sigma,\  \delta,\ q_{0},\ F)</math>
`
* Q ye un cunjunto fenito nun bazio de stados de l'outómato;
* \Sigma ye un cunjunto de simblos, chamado alfabeto d'antrada de l'outómato;
* \delta:Q \times \Sigma \to Q ye la funçon de trasiçon de stados de l'outómato i sou papel ye l d'andicar las trasiçones possibles an cada cunfiguraçon de l'outómato. Esta funçon fornece para cada par "stado i simblo d'antrada" un nuobo stado para adonde l'outómato deberá mober-se.
* q_{0}\in\, Q  ye chamado stado enicial de l'outómato fenito. Ye l'estado pa l qual l reconhecedor debe ser liebado antes d'ampeçar sues atebidades.
* F\subseteq Q ye un subconjunto de l cunjunto Q de ls stados de l'outómato, i cuntén todos ls stados d'aceitaçon ó stados finales de l'outómato fenito. Estes stados son aqueilhes an que l'outómato debe treminar l reconhecimiento de las cadeias d'antrada que pertencen a la lenguaige que l'outómato define. Nanhue outra cadeia debe ser capaç de liebar l'outómato la qualquiera destes stados.

Por eisemplo:
` 
M = ({La, B}, {0, 1}, f, La, {B}) 
f = (La, 0) Þ La 
:::: (La, 1) Þ B
:::: (B, 1) Þ B
:::: (B, 0) Þ La
`

Para este outómato fenito, reconhecen-se ls seguintes eilemientos: 

# stados de l'outómato: L'i B
# simblos de l'alfabeto d'antrada: 0 i 1
# stado final: B
# estado enicial: La
# lenguaige reconhecida: cadeias de dígitos binairos treminadas oubrigatoriamente por un dígito 1.

## Outómatos a la pilha (ó pushdown)

San reconhecedores de Lenguaiges Libres de Cuntesto defenidos atrabeç de la sétupla de la forma: 
: `M=(I, B, P, f, q0, z0, F)`Adonde:
* **I** ye un cunjunto fenito nun bazio de stados de l'outómato a la pilha.
* **B** ye un cunjunto fenito nun bazio de simblos d'antrada ó átomos, chamado alfabeto d'antrada de l'outómato a la pilha. Ls simblos d'antrada son ls eilemientos de que son formadas las cadeias d'antrada submetidas al outómato para aceitaçon.
* **P** ye un cunjunto fenito nun bazio de simblos de la pilha, i forma l'alfabeto de la pilha. Ls simblos de la pilha  son ls códigos armazenados pul outómato an sue mimória auxeliar. Esta mimória, ne l causo de l'outómato a la pilha, ye ourganizada na forma dua pilha, ó seia, ls radadeiros dados armazenados son ls purmeiros la séren lidos de la pilha, i al alrobés.
* **f** ye la chamada funçon de trasiçon de l'outómato a la pilha, i ye cumpuosta dun cunjunto de porduçones que definen las regras de mobimentaçon de l'outómato a la pilha. Esta funçon mapeia l perduto cartesiano I X (B Ye {l}) X P ne l perduto cartesiano I X P*. An palabras, dado un stado, un simblo d'antrada i un simblo de pilha cuntido ne l topo de a mimória auxeliar, esta funçon detremina un nuobo estado de l'outómato i l nuobo cuntenido de l topo de la pilha (de cumprimiento qualquiera).
* **q0** ye chamado stado enicial de l'outómato a la pilha, i ye un eilemiento de l cunjunto I. Ye l'estado an que se debe ancontrar l'outómato a la pilha eimediatamente antes de l'ampeço de l reconhecimiento dua cadeia d'antrada (q0 Î I).
* **z0** ye un eilemiento de l cunjunto P, çtinto de ls demales  pula cumbençon de que sue persença, ne l topo de la pilha qu'amplementa a mimória de l'outómato, andica l'auséncia d'outros eilemientos na mesma. Ye un marcador de pilha bazie (z0 Î P).
* **F** ye un subconjunto de l cunjunto de stados I de l'outómato, que cuntén  todos ls chamados stados finales ó stados d'aceitaçon de l'outómato de pilha. Tales stados corresponden  àqueles ne ls quales l'outómato de pilha debe ancerrar l reconhecimiento de  todas las cadeias d'antrada que séian sentenças de la lenguaige defenida pul outómato a la pilha. Nanhue outra cadeia debe finalizar l'outómato an qualquiera destes stados.

Por eisemplo: 
`
: M = ( { La, B, C}, {0, 1}, {x, y},
:::::::::: { f(La, 1, y) Þ (La, yx),
:::::::::::: f(La, 1, x) Þ (La, xx)
:::::::::::: f(La, 0, y) Þ (B, y)
:::::::::::: f(La, 0, x) Þ (B, x)
:::::::::::: f(B, 0, x) Þ (B, x)
:::::::::::: f(B, 1, xx) Þ (C, x)
:::::::::::: f(B, 1, yx) Þ (C, y)
:::::::::::: f(C, 1, xx) Þ (C, x)
:::::::::::: f(C, 1, yx) Þ (C, y) },
::::::::::: La, y, {C} )
`

Este outómato reconhece cadeias binárias de la forma 1^n0+1^m, adonde mi m son anteiros nó-negatibos i la^m simboliza ua cadeia de m simblos la seguidos. 

Ous.: La cada trasiçon, ua sequéncia fenita de simblos de P ye anserida na pilha, sustituindo l simblo de l topo. Se la sequéncia fur l, eiquibale a l'açon "zampilhar". L'anserçon ye tal que l simblo mais a la squierda queda ne l topo de la pilha.

## Ber tamien

* Teorie de Outómatos
* Máquina de stado fenito
* Planeijamiento Outomatizado

## Softwares
* .com Simulador de Outómatos - Software para criaçon, teste i cumberson de Modelos Formales. Cun anterface gráfica.
* SCTMF - Software para Criaçon i Teste de Modelos Formales.
* JFlap - Software amaricano para testes cun anterface gráfica.

## Refréncias
Outómatos fenitos