Autómatas

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.
¿Qué es un autómata?
Un autómata es un modelo matemático para una máquina de estado finito, en el que
dada una entrada de símbolos, “salta” mediante una serie de estados de acuerdo a una
función de transición (que puede ser expresada como una tabla). Esta función de
transición indica a qué estado cambiar dados el estado actual y el símbolo leído.
Autómata finito determinista

Es un autómata finito que además es un sistema determinista; es decir, para cada estado
en que se encuentre el autómata, y con cualquier símbolo del alfabeto leído, existe siempre
no más de una transición posible desde ese estado y con ese símbolo.
Ejemplo
Autómata finito que podría formar parte de un analizador léxico. El trabajo de este autómata
consiste en reconocer la palabra coding, por lo que necesita siete estados, representando
cada uno de ellos la posición que dentro de dicha palabra se haya leído hasta el momento.
Estas posiciones corresponden con los prefijos de la palabra, desde la cadena de

caracteres vacía (es decir, cuando no contiene ningún carácter) hasta la palabra completa.
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.
Definición formal de autómata finito
Sea M un conjunto:
M = (E, A, T, e0, F) donde
● E todos los estados.

● A es el alfabeto de entrada.
● q0 representa el estado inicia que pertenece al conjunto E.
● F los estados finales que están contenidos en E.
● T la función de transición que está dada por: T: E x A -> P(E) donde P(E) es el
conjunto de subconjuntos de E.
Cuando se construye la tabla de transición:
T(e,a) = R significa que si se está en un estado e y se lee un símbolo a puede
cambiar a cualquiera de los estados e’ que pertenecen a R.
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.
Representación o diagrama de un AFD
Representaremos los estados del AFD mediante círculos que encierran el nombre del
estado (q0 , q1 ,...) .
La posible transición δ(qi,x)=qj
δ(qi,x)=qj
se representa mediante una flecha que empieza en qi y termina en qj con la etiqueta "x".
Los circulos de los estados de aceptación tienen el borde doble.
El estado inicial, q0, se representa con una flecha que termina en dicho estado (pero no
empieza en ningún estado).
EJEMPLO 1
Aplicaciones
1. Software para diseñar y probar el comportamiento de circuitos digitales.
2. El “analizador léxico” de un compilador típico, es decir, el componente del compilador
que separa el texto de entrada en unidades lógicas, tal como identificadores, palabras
clave y signos de puntuación.
3. Software para explorar cuerpos de texto largos, como colecciones de páginas web, o
para determinar el número de apariciones de palabras, frases u otros patrones
comúnmente conocidos como expresiones regulares.
4. Software para verificar sistemas de todo tipo que tengan un número finito de estados
diferentes, tales como protocolos de comunicaciones o protocolos para el intercambio
seguro de información.

Autómatas

Cargado por

Copyright:

Formatos disponibles

Autómatas

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Autómatas

Cargado por

Copyright:

Formatos disponibles

Historia

El origen de los autómatas finitos probablemente se remonta a su uso implícito en

Posteriormente, en 1943, surge una primera aproximación formal de los

Autómata finito determinista

Estas posiciones corresponden con los prefijos de la palabra, desde la cadena de

Autómata finito no determinista

● Que existan transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;

Cuando se cumple el segundo caso, se dice que el autómata es un autómata finito

M = (E, A, T, e0, F) donde

● E todos los estados.

Cuando se construye la tabla de transición:

T(e,a) = R significa que si se está en un estado e y se lee un símbolo a puede

cambiar a cualquiera de los estados e’ que pertenecen a R.

Equivalencias entre autómatas finitos

También podría gustarte