http://www.comoustedyasabe.com.ar/2docuatrimestre/ciencias/ClaseAutomatasFinitos.pps
AUTOMATAS FINITOS
Un autómata finito es un modelo matemático de una máquina que acepta cadenas de un
lenguaje definido sobre un alfabeto A. Consiste en un conjunto finito de estados y un conjunto
de transiciones entre esos estados, que dependen de los símbolos de la cadena de entrada. El
autómata finito acepta una cadena x si la secuencia de transiciones correspondientes a los
símbolos de x conduce desde el estado inicial a un estado final.
Si para todo estado del autómata existe como máximo una transición definida para cada
símbolo del alfabeto, se dice que el autómata es determinístico (AFD). Si a partir de algún
estado y para el mismo símbolo de entrada, se definen dos o más transiciones se dice que el
autómata es no determinístico (AFND).
Formalmente un autómata finito se define como una 5-upla
M =
E: conjunto finito de estados
A: alfabeto o conjunto finito de símbolos de entrada
d: función de transición de estados, que se define como
- d: E x A ® E si el autómata es determinístico
- d: E x A ® P(E) si el autómata es no determinístico (P(E) es el conjunto potencia
de E, es decir el conjunto de todos los subconjuntos de E)
e0: estado inicial; e0 Î E
F: conjunto de estados finales o estados de aceptación; F Í E
Generalmente se asocia con cada autómata un grafo dirigido, llamado diagrama de transición
de estados. Cada nodo del grafo corresponde a un estado. El estado inicial se indica mediante
una flecha que no tiene nodo origen. Los estados finales se representan con un círculo doble.
Si existe una transición del estado ei al estado ej para un símbolo de entrada a, existe entonces
un arco rotulado a desde el nodo ei al nodo ej; es decir que d(ei, a) = ej, se representa en el
diagrama
Ejemplo 1:
Autómata finito determinístico que acepta el lenguaje
L1 = {ancbm/ n > 0 y m ³ 0 }
M1D = < {e0, e1, e2}, {a, b, c}, d1D, e0, {e2 }>
d1D está definida por el siguiente diagrama de transición de estados
Ejemplo 2:
Autómata finito determinístico que acepta el lenguaje.
Autómatas finitos deterministas
Un AFD o autómata finito determinista es aquel autómata finito cuyo estado de llegada está unívocamente determinado por el estado inicial y el carácter leído por el autómata. Formalmente, un autómata finito determinista (AFD) es similar a un Autómata de estados finitos, representado con una 5-tupla (S,Σ,T,s,A) donde:
• Σ es un alfabeto; • S un conjunto de estados; • T es la función de transición: ; • es el estado inicial; • es un conjunto de estados de aceptación o finales.
Al contrario de la definición de autómata finito, este es un caso particular donde no se permiten transiciones lambda (vacías), el dominio de la función T es S (con lo cual no se permiten transiciones desde un estado de un mismo símbolo a varios estados).
A partir de este autómata finito es posible hallar la expresión regular resolviendo un sistema de ecuaciones. S1 = 1 S1 + 0 S2 + ε
S2 = 1 S2 + 0 S1+
Siendo ε la palabra nula. Resolviendo el sistema y haciendo uso de las reducciones apropiadas se obtiene la siguiente expresión regular: 1*(01*01*)*. Inversamente, dada la expresión regular es posible generar un autómata que reconozca el lenguaje en cuestión utilizando el algoritmo de Thompson, desarrollado por Ken Thompson, uno de los principales creadores de UNIX, junto con Dennis Ritchie. Un tipo de autómatas finitos deterministas interesantes son los tries.
Autómatas finitos no deterministas
Un AFND o autómata finito no determinista es aquel que presenta cero, una o más transiciones por el mismo carácter del alfabeto . Un autómata finito no determinista también puede o no tener más de un nodo inicial. Los AFND también se representan formalmente como tuplas de 5 elementos (S,Σ,T,s,A). La única diferencia respecto al AFD es T.
AFD: AFND: (partes de S)
Debido a que la función de transición lleva a un conjunto de estados, el automáta puede estar en varios estados a la vez (o en ninguno si se trata del conjunto vacío de estados). Autómatas finitos no deterministas con transiciones λ Un AFND-λ o autómata finito no determinista con transiciones λ permite cambiar de estado sin procesar ningún símbolo de entrada. Cuando el autómata llega a un estado, se encuentra en ese estado y en los estados a los que apunte este mediante una transición λ.
Un automata es un AFND: (partes de S) AFND-λ: (partes de S)
Cuando el símbolo de entrada es la palabra vacía (λ), existe una transición λ entre los estados. AFD, AFND y AFND-λ Para todo AFND-λ existe un AFND equivalente y para todo AFND existe un AFD equivalente.
Existen algoritmos para transformar un autómata en otro. Los AFD son los más sencillos de construir, por tanto, puede ser útil diseñar un autómata complejo como AFND-λ o AFND para luego transformarlo en AFD para su implementación.
AFD: AFND: (partes de S)
Debido a que la función de transición lleva a un conjunto de estados, el automáta puede estar en varios estados a la vez (o en ninguno si se trata del conjunto vacío de estados). Autómatas finitos no deterministas con transiciones λ Un AFND-λ o autómata finito no determinista con transiciones λ permite cambiar de estado sin procesar ningún símbolo de entrada. Cuando el autómata llega a un estado, se encuentra en ese estado y en los estados a los que apunte este mediante una transición λ.
Un automata es un AFND: (partes de S) AFND-λ: (partes de S)
Cuando el símbolo de entrada es la palabra vacía (λ), existe una transición λ entre los estados. AFD, AFND y AFND-λ Para todo AFND-λ existe un AFND equivalente y para todo AFND existe un AFD equivalente.
Existen algoritmos para transformar un autómata en otro. Los AFD son los más sencillos de construir, por tanto, puede ser útil diseñar un autómata complejo como AFND-λ o AFND para luego transformarlo en AFD para su implementación.
