Autómata finito
Páginas: 13 (3081 palabras)
Publicado: 22 de agosto de 2014
Un autómata finito (AF) o máquina de estado finito es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida.
Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena decaracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida.
La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de Chomsky.Índice [ocultar]
1 Historia
2 Definición formal
2.1 Representación como diagramas de estados
2.2 Representación como tabla de transiciones
2.3 Funcionamiento
2.4 Generalización de la función de transición
3 Autómata finito determinista
4 Autómata finito no determinista
5 Equivalencias entre autómatas finitos
5.1 Conversión de un AFND-ε a un AFND
5.2 Conversión de un AFND a un AFD
5.3Minimización de un AFD
6 Generalizaciones de autómatas finitos
7 Véase también
8 Referencias
8.1 Bibliografía
9 Enlaces externos
Historia[editar]
El modelo neuronal de McCulloch-Pitts también utiliza diagramas con estados y transiciones, además de los conceptos de entrada y salida.
El origen de los autómatas finitos probablemente se remonta a su uso implícito en máquinas electromecánicas,desde principios del siglo XX.1 Ya en 1907, el matemático ruso Andréi Márkov formalizó un proceso llamado cadena de Markov, donde la ocurrencia de cada evento depende con una cierta probabilidad del evento anterior.2 Esta capacidad de "recordar" es utilizada posteriormente por los autómatas finitos, que poseen una memoria primitiva similar, en que la activación de un estado también depende delestado anterior, así como del símbolo o palabra presente en la función de transición.
Posteriormente, en 1943, surge una primera aproximación formal de los autómatas finitos con el modelo neuronal de McCulloch-Pitts. Durante la década de 1950 prolifera su estudio, frecuentemente llamándoseles máquinas de secuencia; se establecen muchas de sus propiedades básicas, incluyendo su interpretación comolenguajes regulares y su equivalencia con las expresiones regulares.1 Al final de esta década, en 1959, surge el concepto de autómata finito no determinista en manos de los informáticos teóricos Michael O. Rabin y Dana Scott.3
En la década de 1960 se establece su conexión con las series de potencias y los sistemas de sobreescritura.4 Finalmente, con el desarrollo del sistema operativo Unix en ladécada de 1970, los autómatas finitos encuentran su nicho en el uso masivo de expresiones regulares para fines prácticos, específicamente en el diseño de analizadores léxicos (comando lex) y la búsqueda y reemplazo de texto (comandos ed y grep).5 A partir de ese tiempo, los autómatas finitos también se comienzan a utilizar en sistemas dinámicos.1
Definición formal[editar]
Formalmente, unautómata finito es una 5-tupla (Q, Σ, q0, δ, F) donde:6
Q\, es un conjunto finito de estados;
\Sigma\, es un alfabeto finito;
q_0\in Q es el estado inicial;
\delta\colon Q\times\Sigma\to Q es una función de transición;
F \subseteq Q es un conjunto de estados finales o de aceptación.
Representación como diagramas de estados[editar]
Este autómata finito está definido sobre el alfabetoΣ={0,1}, posee dos estados s1 y s2, y sus transiciones son δ(s1,0)=s2, δ(s1,1)=s1, δ(s2,0)=s1 y δ(s2,1)=s2. Su estado inicial es s1, que es también su único estado final.
Los autómatas finitos se pueden representar mediante grafos particulares, también llamados diagramas de estados finitos, de la siguiente manera:
Los estados Q se representan como vértices, etiquetados con su nombre en el...
Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena decaracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida.
La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de Chomsky.Índice [ocultar]
1 Historia
2 Definición formal
2.1 Representación como diagramas de estados
2.2 Representación como tabla de transiciones
2.3 Funcionamiento
2.4 Generalización de la función de transición
3 Autómata finito determinista
4 Autómata finito no determinista
5 Equivalencias entre autómatas finitos
5.1 Conversión de un AFND-ε a un AFND
5.2 Conversión de un AFND a un AFD
5.3Minimización de un AFD
6 Generalizaciones de autómatas finitos
7 Véase también
8 Referencias
8.1 Bibliografía
9 Enlaces externos
Historia[editar]
El modelo neuronal de McCulloch-Pitts también utiliza diagramas con estados y transiciones, además de los conceptos de entrada y salida.
El origen de los autómatas finitos probablemente se remonta a su uso implícito en máquinas electromecánicas,desde principios del siglo XX.1 Ya en 1907, el matemático ruso Andréi Márkov formalizó un proceso llamado cadena de Markov, donde la ocurrencia de cada evento depende con una cierta probabilidad del evento anterior.2 Esta capacidad de "recordar" es utilizada posteriormente por los autómatas finitos, que poseen una memoria primitiva similar, en que la activación de un estado también depende delestado anterior, así como del símbolo o palabra presente en la función de transición.
Posteriormente, en 1943, surge una primera aproximación formal de los autómatas finitos con el modelo neuronal de McCulloch-Pitts. Durante la década de 1950 prolifera su estudio, frecuentemente llamándoseles máquinas de secuencia; se establecen muchas de sus propiedades básicas, incluyendo su interpretación comolenguajes regulares y su equivalencia con las expresiones regulares.1 Al final de esta década, en 1959, surge el concepto de autómata finito no determinista en manos de los informáticos teóricos Michael O. Rabin y Dana Scott.3
En la década de 1960 se establece su conexión con las series de potencias y los sistemas de sobreescritura.4 Finalmente, con el desarrollo del sistema operativo Unix en ladécada de 1970, los autómatas finitos encuentran su nicho en el uso masivo de expresiones regulares para fines prácticos, específicamente en el diseño de analizadores léxicos (comando lex) y la búsqueda y reemplazo de texto (comandos ed y grep).5 A partir de ese tiempo, los autómatas finitos también se comienzan a utilizar en sistemas dinámicos.1
Definición formal[editar]
Formalmente, unautómata finito es una 5-tupla (Q, Σ, q0, δ, F) donde:6
Q\, es un conjunto finito de estados;
\Sigma\, es un alfabeto finito;
q_0\in Q es el estado inicial;
\delta\colon Q\times\Sigma\to Q es una función de transición;
F \subseteq Q es un conjunto de estados finales o de aceptación.
Representación como diagramas de estados[editar]
Este autómata finito está definido sobre el alfabetoΣ={0,1}, posee dos estados s1 y s2, y sus transiciones son δ(s1,0)=s2, δ(s1,1)=s1, δ(s2,0)=s1 y δ(s2,1)=s2. Su estado inicial es s1, que es también su único estado final.
Los autómatas finitos se pueden representar mediante grafos particulares, también llamados diagramas de estados finitos, de la siguiente manera:
Los estados Q se representan como vértices, etiquetados con su nombre en el...
Leer documento completo
Regístrate para leer el documento completo.