Automatas

Ojala les sirvan estas unidades













UNIDAD 3.- AUTÓMATAS FINITOS

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 sebasa 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, quecorresponden a los lenguajes formales más simples según la Jerarquía de Chomsky.
3.1 DEFINICIÓN FORMAL
Formalmente, un autómata finito es una 5-tupla (Q, Σ, q0, δ, F) donde:6
 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.

3.2 CLASIFICACION AF
Los autómatas se puedenclasificar en:
Deterministas
Cada combinación (estado, símbolo de entrada) produce un solo estado.

No Deterministas
Cada combinación (estado, símbolo de entrada) produce varios estados y además son posibles las transiciones con λ.
Autómatas finitos deterministas (AFD)
• Determinista: para cada entrada, existe un único estado al que
el autómata puede llegar partiendo del estado actual
•Consta de:
– un conjunto finito de estados, Q
– un conjunto finito de símbolos de entrada, Σ
– una función de transición (δ) que, dados un estado y una entrada,
devuelve un estado. δ(q, a) = p
– un estado inicial (uno de los estados de Q), q0
– un conjunto de estados finales o de aceptación (subconjunto de Q), F
• A = (Q, Σ, δ, q0, F)
3.3 CONVERSIÓN DE UN AFN EN UN AFD
 Para convertir un AFDen un AFN que reconozca el mismo lenguaje. Este algoritmo, a menudo es llamado construcción de subconjuntos, es útil para simular un AFN por medio de un programa de computadora.  
En la tabla de transiciones de un AFN, cada entrada es un conjunto de estados; en la tabla de transiciones de un AFD, cada entrada es tan solo un estado. La idea general tras la construcción AFN a AFD es que cadaestado de AFD corresponde a un conjunto de estados del AFN. El AFD utiliza un estado para localizar todos los posibles estados en los que puede estar el AFN después de leer cada símbolo de la entrada. Es decir, después de leer la entrara a1, a2,. ..an, el AFD se encuentra en un estado que representa al subconjunto T de los estados del AFN alcanzables desde el estado de inicio del AFN a lo largo dealgún camino etiquetado con a1, a2,. ..an. El número de estados de AFD puede ser exponencialmente en el número de estados del AFN pero en la práctica este peor caso ocurre raramente. 
Algoritmo (Construcción de subconjuntos) Construcción de un AFD a partir de un AFN.
Entrada. Un AFN N
Salida. Un AFD D que acepta el mismo lenguaje
Método. El algoritmo construye una tabla de transiciones tranD paraD. Cada estado del AFD es un conjunto de estados del AFN y se construye tranD de modo que D simulará "en paralelo" todos los posibles movimientos que N puede realizar con una determinada cadena de entrada.
Se utilizan las operaciones de la siguiente tabla para localizar los conjuntos de los estados del AFN (s representa un estado del AFN, y T un conjunto de estados del AFN). 
OperaciónDescripción
Cerradura- (s)
Conjunto de estados del AFN alcanzables desde el estado s del AFN con transiciones  solamente
Cerradura- (T)
Conjunto de estados del AFN alcanzables desde algún estado s en T con transiciones  solamente.
mueve(T, a)
Conjunto de estados del AFN hacia los cuales hay una transición con el símbolo de entrada a desde algún estado s en T del AFN
 Antes de detectar el...