Please enable JavaScript.
Coggle requires JavaScript to display documents.
Teoria de Lenguajes Formales y Automatas - Coggle Diagram
Teoria de Lenguajes Formales y Automatas
UNIDAD 1: Elementos Atomicos y Operaciones sobre Lenguajes
Fundamentos Sintacticos
Cuerda / Cadena: Secuencia finita de símbolos del Alfabeto
Cadena Vacía: Cadena de longitud cero
Alfabeto: Conjunto finito y no vacío de símbolos.
Longitud: Número de símbolos en la cuerda.
Clausuras y Operaciones de Lenguajes
Clausura Positiva: excluye unicamente a la cadena vacía
Operaciones entre Lenguajes: Unión, Concatenación , Intersección, Complemento
Clausura de Kleene: Conjunto de todas las cadenas posibles, incluyendo la cadena vacia
UNIDAD 2: Automatas Finitos Deterministicos (AFD)
Formas de Representacion
Grafo de Transicion (Diagrama de Estados): Nodos = Estados; Flecha sin origen = Estado inicial; Doble círculo = Estado de aceptación
Tabla / Matriz de Transicion: Filas = Estados; Columnas = Símbolos del alfabeto
Procesamiento de Cadenas
Cadena Aceptada: La lectura de la cadena finaliza en un estado perteneciente a los estados finales
Cadena Rechazada: La lectura finaliza en un estado fuera de los estados finales
Estructura Matematica
Función de transición determinística
Estado inicial
Alfabeto de entrada.
Conjunto de estados de aceptación/finales
Conjunto finito de estados.
UNIDAD 4: Optimizacion de AFD y Expresiones Regulares (ER)
Expresiones Regulares (ER)
Definición: Representación algebraica de Lenguajes Regulares usando unión, concatenación y estrella de Kleene
Conversion ER $\rightarrow$ AFN (Algoritmo de Thompson): Construcción modular de máquinas de estados usando bloques para símbolos individuales
Conversion AF $\rightarrow$ ER (Eliminacion de Estados)
Propiedades y Verificaciones de Lenguajes
Algoritmo de Equivalencia entre AFDs: Comparación de pares de estados desde los iniciales para verificar concordancia en aceptación
Lema del Bombeo (Pumping Lemma)
Analisis y Simplificacion de Estados
Estados Inservibles
Inaccesibles: No se pueden alcanzar desde el estado inicial
Trampa / Absorbente: Alcanzables pero no permiten llegar a un estado de aceptación.
Estados Indistinguibles: Dos estados que producen exactamente el mismo comportamiento de aceptación/rechazo para cualquier cadena futura.
Algoritmo de Minimizacion Top-Down (Refinamiento de Particiones)
UNIDAD 3: Automatas Finitos No Deterministicos (AFN)
Caracteristicas del No Determinismo
Transiciones Vacías: Transiciones sin consumir ningún símbolo de entrada
Funcion de Transicion Extendida
Transiciones Multiples: Desde un estado y con un mismo símbolo se puede ir a cero, uno o más estados.
Algoritmo de Equivalencia / Conversion
Paso 2: Evaluar las transiciones hacia nuevos conjuntos de estados para cada símbolo del alfabeto
Paso 3: Repetir hasta no generar nuevos conjuntos (los conjuntos pasan a ser los estados del AFD final)
Paso 1: Calcular la clausura del estado inicial.