AUTOMATAS FINITOS. UNIDAD 3. CLASIFICACION AF Y CONVERSIÓN DE UN AFND A UN AFD




INSTITUTO TECNOLOGICO DE TAPACHULA




INGENIERIA EN SISTEMAS COMPUTACIONALES




LENGUAJE Y AUTOMATAS I




ROSEMBERG LOPEZ JIMENEZ


UNIDAD III



AUTOMATAS FINITOS



LUIS MANUEL PEREZ JIMENEZ



SEMESTRE: 6 GRUPO: C




TAPACHULA, CHIAPAS A 26 DE MAYO DEL 2013.

INTRODUCCION


En esta unidad veremos que son los autómatas finitos. Tantocomo su clasificación, representación, minimización hasta su conversión. Se podría decir que los autómatas finitos 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 basaen 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. Un autómata finito o máquina de estado finito es un modelo matemático de un sistema querecibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce.
















3.1 DEFINICIÓN FORMAL

Un autómata finito o máquina de estado finito es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómatareconoce.
Formalmente, un autómata finito (AF) puede ser descrito como una 5-tupla (S,Σ,T,s,A) donde:

S un conjunto de estados;
Σ es un alfabeto;
T es la función de transición: ;
es el estado inicial;
es un conjunto de estados de aceptación o finales.

Ejemplo 1

S = {S1, S2},
Σ = {0,1},
T = {(S1,0,{S2});(S1,1,{S1});(S2,0,{S1});(S2,1,{S2})}
s = S1
A = {S1}.



Un autómatafinito o máquina de estado finito es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce.

Éstos se definen mediante una quíntupla (E, Q, f, q0, F) donde:

E: alfabeto de entrada.
Q: conjunto de estados; es conjunto finito no vacío.
f: función de transición. f(p,a)=q
q0 :(perteneciente a Q) estado inicial.
F: (perteneciente a Q) conjunto de estados finales o de aceptación.









3.2 CLASIFICACION AF


Los autómatas se pueden clasificar 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 transicionescon λ.




























3.3 CONVERSIÓN DE UN AFND A UN AFD



Conversión de un AFND a un AFD.




AFND inicial.




Proceso de conversión.




AFD final.

Todo AFND (QN, Σ, q0, δN, FN) puede convertirse en un AFD (QD, Σ, q0, δD, FD) equivalente, que mantiene el alfabeto Σ y el estado inicial q0 originales. La conversión implica pasar porun AFD intermedio con estados y transiciones redundantes, que al no ser accesibles a partir del estado inicial, son eliminados para obtener el AFD definitivo.
Para definir el AFD intermedio, se deben seguir los siguientes pasos:
1. Primero se redefine el conjunto de estados QN = {q0, q1, ..., qm} original, como uno conformado por todos los subconjuntos de QN. Los nuevos estados finales serántodos aquellos estados que contengan a alguno de los estados finales originales.
2. Posteriormente, se redefine el conjunto de transiciones original, por transiciones del tipo δD(S,a), donde a∈Σ, y S es la unión de todos los estados q de QN para los cuales existía la transición δN(q,a).
3. Por último, se eliminan los estados inaccesibles o inalcanzables (junto con sus transiciones de salida), es...