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

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

Propiedades de clausura, lema del bombeo y minimización

PROPIEDADES DE CLAUSURA

La clase de los lenguajes regulares es cerrada bajo unión, concatenación, estrella, complemento, intersección, diferencia y reverso. Son herramientas de demostración: permiten probar regularidad sin construir el autómata.

• Complemento: intercambiar estados de aceptación en un AFD con δ total. Solo funciona sobre un AFD, nunca sobre un AFN.
• Intersección: construcción del producto, con estados que son pares y simulación en paralelo.

EL LEMA DEL BOMBEO

Todo lo anterior sirve para probar que un lenguaje sí es regular. El lema del bombeo sirve para lo contrario.

Si L es regular, existe p ≥ 1 tal que toda w ∈ L con |w| ≥ p puede escribirse w = xyz con |y| ≥ 1, |xy| ≤ p, y xyⁱz ∈ L para todo i ≥ 0.

DE DÓNDE SALE

Si el autómata tiene p estados y la cadena tiene al menos p símbolos, por el principio del palomar algún estado se repite dentro de los primeros p pasos. El tramo entre esas dos visitas es un ciclo, y un ciclo se puede recorrer las veces que se quiera. Ese tramo es y.

CÓMO SE USA: ES UN JUEGO

1. El adversario elige p, que no conoces.

2. Tú eliges una w ∈ L con |w| ≥ p, en función de p.

3. El adversario descompone w = xyz respetando las dos primeras condiciones.

4. Tú eliges un i que saque a xyⁱz de L.

La clave está en el paso 2: elegir una w que restrinja al máximo las descomposiciones posibles.

EJEMPLO CANÓNICO

L = {0ⁿ1ⁿ} no es regular. Se toma w = 0^p 1^p. Como |xy| ≤ p, tanto x como y constan solo de ceros. Con i = 2 se agregan ceros sin agregar unos y la cadena sale de L.

Compáralo con la sesión 5: una máquina de Turing reconoce este lenguaje sin dificultad. Aquí queda demostrado, y no solo intuido, que el autómata finito es estrictamente menos potente.

MINIMIZACIÓN DE AFD

Por el teorema de Myhill-Nerode, para cada lenguaje regular existe un AFD mínimo único salvo renombramiento. Se calcula con el algoritmo de llenado de tabla: se marcan los pares distinguibles y se fusionan los que quedan sin marcar.

• Reduce memoria en los analizadores léxicos que se generan.
• Permite decidir si dos autómatas o dos expresiones regulares son equivalentes.

EJERCICIO

Probar que {ww} y {0ⁿ | n primo} no son regulares; minimizar dos AFD y usar el resultado para decidir equivalencia.