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

NE111 · lunes 12/10/2026 · 16:00-17:15 · Sesión 18

Autómatas finitos deterministas

EL MODELO

Un autómata finito lee la entrada de izquierda a derecha, un símbolo a la vez, sin poder retroceder ni escribir, y su única memoria es en cuál de un número finito de estados se encuentra.

CONTRASTE CON LA MÁQUINA DE TURING

Vale la pena verlo contra lo que ya estudiamos: la MT podía escribir, moverse en ambas direcciones y usar memoria ilimitada. El autómata finito no puede nada de eso. Es el modelo mínimo, y todo el interés está en qué se puede hacer con tan poco.

DEFINICIÓN FORMAL

AFD = (Q, Σ, δ, q₀, F).

• Q — conjunto finito de estados.
• Σ — alfabeto de entrada.
• δ: Q × Σ → Q — función de transición, total: definida para todo par.
• q₀ — estado inicial único. F ⊆ Q — estados de aceptación.

QUÉ SIGNIFICA DETERMINISTA

Para cada estado y cada símbolo hay exactamente una transición: ni cero ni dos. El cómputo sobre una cadena es un camino único, sin decisiones.

ACEPTACIÓN

M acepta w si al consumir w completa termina en un estado de F. El lenguaje L(M) es el conjunto de todas las cadenas que acepta.

DISEÑO: LA PREGUNTA GUÍA

¿Qué necesito recordar de lo ya leído para decidir correctamente sobre lo que falta? La respuesta es el conjunto de estados. Si la respuesta exige información no acotada, no hay AFD posible.

PATRONES FRECUENTES

• Contar módulo k — k estados en ciclo.
• Reconocer un sufijo — los estados indican cuánto del patrón se lleva.
• Reconocer una subcadena en cualquier posición — con estado sumidero de aceptación.
• Estado trampa — para las rutas que llevan a rechazo definitivo, necesario porque δ debe ser total.

LA LIMITACIÓN ESENCIAL

Con memoria finita solo se puede recordar una cantidad acotada de información. No se puede contar sin cota, y por eso 0ⁿ1ⁿ queda fuera. Esa limitación se formalizará con el lema del bombeo.

EJERCICIO

Construir AFD para: cadenas que terminan en 01; que contienen 110; de longitud múltiplo de 3; que representan múltiplos de 3 en binario.