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

NE111 · miércoles 14/10/2026 · 16:00-17:15 · Sesión 19

Autómatas finitos no deterministas

RELAJAR EL DETERMINISMO

Un AFN permite que δ devuelva un conjunto de estados: cero, uno o varios. La máquina explora todas las posibilidades a la vez y acepta si alguna rama termina en aceptación.

DEFINICIÓN FORMAL

AFN = (Q, Σ, δ, q₀, F) con δ: Q × Σ → P(Q), el conjunto potencia de Q.

ACEPTACIÓN EXISTENCIAL

Se acepta si existe al menos un camino que consuma la cadena y termine en F. Basta una rama exitosa aunque todas las demás mueran. Para rechazar, en cambio, deben fallar todas.

TRANSICIONES Ε

Una extensión adicional permite cambiar de estado sin consumir símbolo. Simplifica mucho la composición de autómatas: para unir dos basta un inicial nuevo con transiciones ε a ambos.

• La ε-clausura de q es el conjunto de estados alcanzables desde q usando solo transiciones ε, incluido q.
• Se calcula recursivamente hasta que no se agreguen estados nuevos.

POR QUÉ FACILITA EL DISEÑO

Reconocer «contiene 01 o termina en 11» con un AFD exige combinar ambas condiciones en cada estado. Con un AFN se adivina al inicio cuál se va a cumplir y se construyen dos ramas independientes.

NO HAY GANANCIA DE PODER

Todo AFN tiene un AFD equivalente. El no determinismo es comodidad de notación, no capacidad adicional: los tres modelos —AFD, AFN y AFN con ε— reconocen exactamente los lenguajes regulares.

CONTRASTE CON TURING

Recuerda la sesión 6: en máquinas de Turing el no determinismo tampoco agrega poder, pero la simulación cuesta tiempo exponencial y eso es el problema P contra NP. Aquí la simulación puede costar un número exponencial de estados, pero se hace una sola vez, al construir el autómata. La diferencia es que allá el costo se paga en cada ejecución y aquí en la compilación.

EJERCICIO

Construir AFN para: cadenas que terminan en 010; donde el tercer símbolo desde el final es 1. Comparar el número de estados con el AFD equivalente.