Tarea1 201325560

David Daniel Alvarez Hernandez 201325560 LFP—CARLOS
YOQUE
AUTOMATAS FINITOS

Es una expresión regular que construye diagramas de transiciones.
----Determinista (AFD)

Puede dar reconocedores másrápidos. No posee una transición con épsilon y
solo utiliza una arista etiquetada a que sale de S.
----No Determinista (AFN)

Puede llegar a tener más de una transición para el mismo símbolo de entrada,
sepuede representar por un grafo de transiciones, las tablas en las que se
puede representar tiene ventajas y desventajas como por ejemplo que ocupan
mucho espacio cuando son muchas letras, y aceptauna entrada solo si hay
desde el inicio una entrada de aceptación
Construcción de subconjuntos es un algoritmo para construir un AFN de un
AFD

Formar un AFN a partir de una expresión regular

--seconstruye un autómata para reconocer épsilon y para el alfabeto, luego se
construye un autómata para expresiones que tengan una alteración.

CONSTRUCCION DE THOMPSON:

Entrada : una expresión regular r.Salida: un AFN N que acepte L(r)

David Daniel Alvarez Hernandez 201325560 LFP—CARLOS
YOQUE
Metodo: primero se hace el análisis sintáctico r en sus subexpresiones
constituyentes, luego se construyenlos AFN para cada uno de los símbolos
básicos de r. si un símbolo A aparece varias veces en R, se construye un AFN
independiente en cada caso. Ejemplo de un AFN compuesto N(s|t) se observa
que de i a ftiene que pasar exclusivamente por N(s) o N(t) .
EXPRESION (st)

se observa que el estado de finalización
de N(s) es el estado de inicialización para N(t).
Simulación de un AFN por medio de dospilas
Entrada: un AFN N construido por el algoritmo 3.3 y una cadena de entrada X.
Salida: si , si N acepta a X, o no si no la acepta.
Método: realiza una construcción de subconjuntos en el momento de laejecución, calcula una transición desde el conjunto en curso de estados S al
siguiente conjunto de estado en dos etapas. Primero mueve(S,a), luego calcula
la cerradura “épsilon” de mueve (s,a).
Se...