GUÍA 19-10-26 Teoría de la Computación

NE111 · lunes 19/10/2026 · 16:00-17:15 · Sesión 20

Equivalencias: de AFN a AFD y de expresiones regulares a autómatas

CONSTRUCCIÓN DE SUBCONJUNTOS

Teorema: para todo AFN N existe un AFD D con L(D) = L(N). La demostración es constructiva.

LA IDEA

Un AFN, al procesar una cadena, se encuentra en un conjunto de estados posibles. Ese conjunto es información finita, así que puede ser el estado de un AFD. Cada estado del AFD es un subconjunto de estados del AFN.

• Estado inicial: la ε-clausura de {q₀}.
• δ_D(S, a) = unión de δ_N(q, a) para todo q ∈ S, cerrada bajo ε.
• F_D = los subconjuntos que contienen al menos un estado de F_N.
• ∅ es un estado válido y funciona como trampa.

CONSTRUCCIÓN POR ALCANZABILIDAD

Generar los 2ⁿ subconjuntos es innecesario: casi todos son inalcanzables. Se empieza por el inicial y solo se crean los subconjuntos que aparecen como destino.

TEOREMA DE KLEENE

Un lenguaje es regular si y solo si puede describirse con una expresión regular. Se demuestra en las dos direcciones, ambas constructivas.

DE EXPRESIÓN REGULAR A AUTÓMATA: CONSTRUCCIÓN DE THOMPSON

Se construye un AFN con ε por inducción sobre la estructura de la expresión. Cada pieza tiene un solo estado inicial y uno final, lo que permite componerlas mecánicamente.

• Símbolo a: dos estados y una transición etiquetada a.
• r+s: inicial nuevo con dos transiciones ε y final nuevo al que ambas llegan.
• rs: transición ε del final de r al inicial de s.
• r*: nuevo inicial y final, con ε que rodea y ε que retroalimenta.

El autómata resultante tiene a lo sumo 2m estados para una expresión de m símbolos. Es exactamente lo que hace un motor de expresiones regulares al compilar un patrón, y es el primer paso del generador de analizadores léxicos.

DE AUTÓMATA A EXPRESIÓN REGULAR: ELIMINACIÓN DE ESTADOS

Se eliminan los estados intermedios uno por uno, reemplazando cada camino que pasaba por el estado eliminado por una expresión que incluye su ciclo propio con estrella. Si p → q con R, q → q con S y q → r con T, al eliminar q queda p → r con RS*T.

EJERCICIO

Aplicar Thompson a (a+b)*abb, determinizar el resultado y comparar con un AFD construido a mano.