Autómata finito - Historial de revisiones

Olga ciget.pinardelrio en 18:20 16 oct 2019

2019-10-16T18:20:55Z

Jhonlier12017 jc.hlg: /* Definición formal */

2013-11-04T16:00:37Z

‎Definición formal

Jhonlier12017 jc.hlg: /* Definición formal */

2013-11-04T15:35:29Z

‎Definición formal

Olaidis ssp.jc en 16:12 14 ene 2013

2013-01-14T16:12:26Z

Olaidis ssp.jc en 16:09 14 ene 2013

2013-01-14T16:09:59Z

Olaidis ssp.jc: Página creada con '{{Definición |Nombre= Autómata finito |imagen=Autómata_F.JPG‎ |tamaño= |concepto= }}
'''Autómata finito'''(máquina de estado finito). Es un mo...'

2013-01-14T16:05:33Z

Página creada con '{{Definición |Nombre= Autómata finito |imagen=Autómata_F.JPG‎ |tamaño= |concepto= }}<div align="justify"> '''Autómata finito'''(máquina de estado finito). Es un mo...'

Página nueva

{{Definición
|Nombre= Autómata finito
|imagen=Autómata_F.JPG‎
|tamaño=
|concepto=
}}<div align="justify">
'''Autómata finito'''([[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]] de caracteres 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.

==Historia==
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. 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. 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 del estado 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 como lenguajes regulares y su equivalencia con las expresiones regulares. 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.
En la década de 1960 se establece su conexión con las series de potencias y los sistemas de sobreescritura. Finalmente, con el desarrollo del sistema operativo Unix en la dé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). A partir de ese tiempo, los autómatas finitos también se comienzan a utilizar en sistemas dinámicos.

==Definición formal==
Formalmente, un autómata finito es una 5-tupla (Q, Σ, q0, δ, F) donde:
* Es un conjunto finito de estados;
* Es un alfabeto finito;
* Es el estado inicial;
* Es una función de transición;
* Es un conjunto de estados finales o de aceptación.

==Autómata finito determinista==
Un autómata finito determinista (AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado q ∈ Q en que se encuentre el autómata, y con cualquier símbolo a ∈ Σ del alfabeto leído, existe siempre a lo más una transición posible δ(q,a).

En un AFD no pueden darse ninguno de estos dos casos:
* Que existan dos transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;
* Que existan transiciones del tipo δ(q,ε), salvo que q sea un estado final, sin transiciones hacia otros estados.

Un ejemplo interesante de autómatas finitos deterministas son los tries.

==Autómata finito no determinista==
Un autómata finito no determinista (AFND) es aquel que, a diferencia de los autómatas finitos deterministas, posee al menos un estado q ∈Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible.

Haciendo la analogía con los AFDs, en un AFND puede darse cualquiera de estos dos casos:
* Que existan transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;
* Que existan transiciones del tipo δ(q,ε), siendo q un estado no-final, o bien un estado final pero con transiciones hacia otros estados.

Cuando se cumple el segundo caso, se dice que el autómata es un autómata finito no determinista con transiciones vacías o transiciones ε (abreviado AFND-ε). Estas transiciones permiten al autómata cambiar de estado sin procesar ningún símbolo de entrada.

==Equivalencias entre autómatas finitos==
Se dice que dos autómatas finitos son equivalentes, si ambos reconocen el mismo lenguaje regular.

Toda expresión regular (que define a su vez un lenguaje regular) puede ser expresada como un autómata finito determinista, y viceversa. Dada una expresión regular, es posible construir un AFND-ε que reconozca dicho lenguaje, por ejemplo mediante el algoritmo de Thompson. Luego, todo AFND-ε puede transformarse en un AFND equivalente, así como todo AFND puede transformarse en un AFD equivalente, mediante el método llamado construcción de conjunto potencia. Así, por transitividad, para cualquier autómata finito no determinista siempre existe un autómata finito determinista equivalente, y viceversa.
Normalmente en el diseño de autómatas finitos, lo primero que se hace es construir un AFND-ε, que es el más sencillo de construir, por poseer menos restricciones en su función de transiciones. Luego dicho autómata se reduce a un AFND, y finalmente a un AFD, el cual por sus características deterministas ya puede ser implementado sin problemas utilizando un lenguaje de programación.

==Conversión de un AFND-ε a un AFND==
La conversión de un AFND-ε en un AFND se basa en el concepto de clausura-ε, que corresponde a una clausura transitiva contextualizada en la teoría de autómatas.

Dado un estado q, se llama clausura-ε(q) al conjunto de todos los estados a los que se puede acceder a partir de q, procesándose a lo más un único símbolo de la entrada. Puede definirse recursivamente de la siguiente manera:
* (Base inductiva) Para todo estado q, q ∈ clausura-ε(q).
* (Inducción) Dados dos estados p y r, si p ∈ clausura-ε(q) y r ∈ δ(p,ε), entonces r ∈ clausura-ε(q).

El algoritmo para eliminar las transiciones vacías es el siguiente:
* Se calcula la clausura-ε del estado inicial, formándose un conjunto A que corresponderá al estado inicial del nuevo autómata.
* Para cada símbolo del alfabeto, se verifican los estados alcanzables a partir de algún estado contenido en A, y se calcula la clausura-ε de dichos estados alcanzables. Si dichas clausuras producen nuevos conjuntos distintos de A, estos serán nuevos estados a los que se accederá a partir de A y del símbolo correspondiente.
* Se repite lo anterior para cada nuevo conjunto, hasta que no existan transiciones posibles para ningún símbolo del alfabeto.

==Generalizaciones de autómatas finitos==
Existes diversas generalizaciones posibles de hacer sobre los autómatas finitos, para aumentar su uso y expresividad. Así, por ejemplo, se definen los transductores de estados finitos como autómatas finitos que están dotados además de un alfabeto de salida, distinto al de entrada, y que pueden poseer más de un estado inicial. Las máquinas de Moore y máquinas de Mealy son conocidos ejemplos de transductores, que se utilizan sobre todo para modelar sistemas secuenciales.
Es incluso posible aumentar el poder de cómputo de un autómata finito, permitiendo un alfabeto adicional sobre éste, que actúe sobre una memoria de tipo pila para ser considerada en cada transición. Esta es la idea utilizada por los llamados autómatas con pila, los cuales son capaces de reconocer lenguajes libres de contexto, que están un nivel por sobre los lenguajes regulares en la Jerarquía de Chomsky.

== Fuentes ==
Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey D. (2001) (en inglés). Introduction to Automata Theory, Languages, and Computation. Massachusetts, Estados Unidos: Addison-Wesley.

[[Categoría:Hardware]] [[Category:Robótica]]

@@ Línea 22: / Línea 22: @@
 * ''Σ'' es un alfabeto      finito de símbolos terminales;
 * ''q0'' es el estado inicial en ''Q'';
-* ''δ'' es la relación de transiciones de la forma ''<q<sub>i</sub>,x,q<sub>j</sub>>'' con  ''q<sub>i</sub>'' y ''q<sub>j</sub>>'' como estados de ''Q'' y ''x'', símbolo de ''Σ'' ó puede ser también la cadena vacía;
+* ''δ'' es la relación de transiciones de la forma ''<q<sub>i</sub>,x,q<sub>j</sub>>'' con  ''q<sub>i</sub>'' y ''q<sub>j</sub>'' como estados de ''Q'' y ''x'', símbolo de ''Σ'' ó puede ser también la cadena vacía;
 * ''F'' es el conjunto de estados finales o de aceptación y (evidentemente) subconjunto de ''Q''.

@@ Línea 4: / Línea 4: @@
 |tamaño=
 |concepto=
-}}<div  align="justify">
+}}
 '''Autómata finito''' ([[máquina]] de estado finito). Es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida.
@@ Línea 12: / Línea 12: @@
 ==Historia==
-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. 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. 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 del estado anterior, así como del símbolo o palabra presente en la función de transición.
+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]]. 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. 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 del estado 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 como lenguajes regulares y su equivalencia con las expresiones regulares. 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.
+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 como lenguajes regulares y su equivalencia con las expresiones regulares. 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.
-En la década de 1960 se establece su conexión con las series de potencias y los sistemas de sobreescritura. Finalmente, con el desarrollo del sistema operativo Unix en la dé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). A partir de ese tiempo, los autómatas finitos también se comienzan a utilizar en sistemas dinámicos.
+En la década de [[1960]] se establece su conexión con las series de potencias y los sistemas de sobreescritura. Finalmente, con el desarrollo del sistema operativo Unix en la dé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). A partir de ese tiempo, los autómatas finitos también se comienzan a utilizar en sistemas dinámicos.
 ==Definición formal==

@@ Línea 18: / Línea 18: @@
 ==Definición formal==
-Formalmente, un autómata finito es una 5-tupla (Q, Σ, q0, δ, F) donde:
+Formalmente, un autómata finito es una 5-tupla ''<Q, Σ, q0, δ, F>'' donde:
-* Es un conjunto finito de estados;
+* ''Q'' es un conjunto finito de estados;
-* Es un alfabeto      finito;
+* ''Σ'' es un alfabeto      finito de símbolos terminales;
-* Es el estado inicial;
+* ''q0'' es el estado inicial en ''Q'';
-* Es      una función de transición;
+* ''δ'' es la relación de transiciones de la forma ''<q<sub>i</sub>,x,q<sub>j</sub>>'' con  ''q<sub>i</sub>'' y ''q<sub>j</sub>>'' como estados de ''Q'' y ''x'', símbolo de ''Σ'' ó puede ser también la cadena vacía;
-* Es un conjunto de      estados finales o de aceptación.
+* ''F'' es el conjunto de estados finales o de aceptación y (evidentemente) subconjunto de ''Q''.
 ==Autómata finito determinista==

@@ Línea 5: / Línea 5: @@
 |concepto=
 }}<div  align="justify">
-'''Autómata finito'''([[máquina]] de estado finito). Es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida.
+'''Autómata finito''' ([[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]] de caracteres 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.
@@ Línea 63: / Línea 63: @@
 ==Generalizaciones de autómatas finitos==
 Existes diversas generalizaciones posibles de hacer sobre los autómatas finitos, para aumentar su uso y expresividad. Así, por ejemplo, se definen los transductores de estados finitos como autómatas finitos que están dotados además de un alfabeto de salida, distinto al de entrada, y que pueden poseer más de un estado inicial. Las máquinas de Moore y máquinas de Mealy son conocidos ejemplos de transductores, que se utilizan sobre todo para modelar sistemas secuenciales.
 Es incluso posible aumentar el poder de cómputo de un autómata finito, permitiendo un alfabeto adicional sobre éste, que actúe sobre una memoria de tipo pila para ser considerada en cada transición. Esta es la idea utilizada por los llamados autómatas con pila, los cuales son capaces de reconocer lenguajes libres de contexto, que están un nivel por sobre los lenguajes regulares en la Jerarquía de Chomsky.

@@ Línea 10: / Línea 10: @@
 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.
 ==Historia==
@@ Línea 68: / Línea 67: @@
 == Fuentes ==
 Hopcroft, John;      Motwani, Rajeev; Ullman, Jeffrey D. (2001) (en      inglés). Introduction to Automata Theory, Languages, and      Computation. Massachusetts, Estados Unidos: Addison-Wesley.
-[[Categoría:Hardware]] [[Category:Robótica]]
+[[Category:Ciencias_informáticas]][[Category:Programación]][[Category:Algoritmos]][[Category:Modelos_matemáticos]]

Autómata finito - Historial de revisiones

Olga ciget.pinardelrio en 18:20 16 oct 2019

Jhonlier12017 jc.hlg: /* Definición formal */

Jhonlier12017 jc.hlg: /* Definición formal */

Olaidis ssp.jc en 16:12 14 ene 2013

Olaidis ssp.jc en 16:09 14 ene 2013

Olaidis ssp.jc: Página creada con '{{Definición |Nombre= Autómata finito |imagen=Autómata_F.JPG‎ |tamaño= |concepto= }} '''Autómata finito'''(máquina de estado finito). Es un mo...'

Olaidis ssp.jc: Página creada con '{{Definición |Nombre= Autómata finito |imagen=Autómata_F.JPG‎ |tamaño= |concepto= }}
'''Autómata finito'''(máquina de estado finito). Es un mo...'