ADA 3 1 - Cuadro comparativo AFD vs AFND

Vista previa del material en texto

Instituto Tecnológico Superior 
Progreso 
Dirección General 
Subdirección Académica 
 
 
 
Boulevard Tecnológico de Progreso S/N por 62, Progreso, Yucatán. C.P. 97320 
Tels. 969 934 3023, tecnm.mx | progreso.tecnm.mx 
 
 
 
 
 
 
 
 
 
 Instituto Tecnológico Superior Progreso 
 
CARRERA: 
Ingeniería en Sistemas Computacionales 
 
MATERIA: 
Lenguajes y Autómatas I 
 
TAREA: 
Cuadro comparativo AFD vs AFND 
 
MAESTRO: 
DR. Holzen Atocha Martínez García. 
 
ESTUDIANTE: 
Miguel Angel De La Cruz Centeno 
 
SEMESTRE: 
6to SEMESTRE 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Instituto Tecnológico Superior 
Progreso 
Dirección General 
Subdirección Académica 
 
 
 
Boulevard Tecnológico de Progreso S/N por 62, Progreso, Yucatán. C.P. 97320 
Tels. 969 934 3023, tecnm.mx | progreso.tecnm.mx 
 
Cuadro comparativo AFD vs AFND 
AUTÓMATAS DETERMINISTAS (AFD) AUTÓMATAS NO DETERMINISTAS (AFND) 
Es un autómata finito en donde δ (delta) es 
una función de transición, es decir, que 
para cada par (estado actual y símbolo de 
entrada) le corresponde un único estado 
siguiente. 
Es un autómata finito en donde δ no es 
necesariamente una función de transición, 
es decir, que para cada par (estado actual 
y símbolo de entrada) le corresponde 
cero, uno, dos o más estados siguientes, 
Normalmente la relación de transición para 
un AFND se denota con ∆ 
La transición desde un estado puede tener 
como destino un único estado. Por eso se 
llama determinista. 
No se aceptan transiciones con cadenas 
vacías. 
Se permite el uso de backtracking. 
Requiere más espacio. 
Una cadena es aceptada si su transición 
es hacia un estado final. 
La transición desde un estado puede tener 
múltiples destinos. Por eso se le llama no 
determinista. 
Permite transiciones con cadenas vacías. 
No siempre se permite el uso de 
backtracking. 
Requiere menos espacio. 
Una cadena es aceptada si solo una de 
todas sus posibles transiciones son hacia 
un estado final. 
AFD son menos complejos que AFND ya 
que tiene una única transición para cada 
entrada en un estado dado 
AFD son más complejos que AFD porque 
pueden tener múltiples transiciones para 
una entrada dada en un estado dado, lo 
que significa que puede haber múltiples 
caminos para procesar una entrada.