GUÍA 09-11-26 Teoría de la Computación

NE111 · lunes 09/11/2026 · 16:00-17:15 · Sesión 26

Lenguajes: autómatas de pila y la jerarquía de Chomsky

LA MÁQUINA DE LAS GRAMÁTICAS LIBRES DE CONTEXTO

Un autómata de pila es un autómata finito con una pila de capacidad ilimitada. Esa pila es la memoria que permite reconocer anidamiento, que es justo lo que le faltaba al autómata finito.

DEFINICIÓN FORMAL

AP = (Q, Σ, Γ, δ, q₀, Z₀, F), con Γ el alfabeto de pila y Z₀ el símbolo inicial de pila.

• Una transición lee estado, símbolo de entrada y tope de pila, y produce nuevo estado más una cadena que reemplaza al tope.
• Reemplazar el tope por ε es desapilar; por sí mismo es no tocar la pila; por dos o más símbolos es apilar.

EJEMPLO

AP para {0ⁿ1ⁿ}: mientras se leen ceros se apilan; al llegar el primer uno se cambia de estado y por cada uno se desapila un cero. Se acepta si al terminar la entrada la pila quedó vacía.

EQUIVALENCIA CON LAS GRAMÁTICAS

Un lenguaje es libre de contexto si y solo si es reconocido por algún autómata de pila. De gramática a autómata: se apila el símbolo inicial y se simulan derivaciones por la izquierda, adivinando qué producción usar.

AQUÍ EL NO DETERMINISMO SÍ AGREGA PODER

A diferencia de los autómatas finitos, los AP deterministas reconocen estrictamente menos que los no deterministas. Los palíndromos, por ejemplo, requieren no determinismo porque no se sabe dónde está el centro.

Los lenguajes de programación se diseñan deliberadamente para caer en la clase determinista, porque solo esa se puede analizar eficientemente. Es una decisión de ingeniería fundada en teoría.

LEMA DEL BOMBEO PARA LIBRES DE CONTEXTO

Si L es libre de contexto, existe p tal que toda z con |z| ≥ p se escribe z = uvwxy con |vx| ≥ 1, |vwx| ≤ p, y uvⁱwxⁱy ∈ L para todo i. Se bombean dos bloques a la vez, porque el ciclo está en un árbol y no en un camino lineal.

Con él se demuestra que {aⁿbⁿcⁿ} no es libre de contexto. Compáralo con la sesión 5: la máquina de Turing lo reconocía sin dificultad.

LA JERARQUÍA DE CHOMSKY

• Tipo 3 — regulares, reconocidos por autómatas finitos.
• Tipo 2 — libres de contexto, por autómatas de pila.
• Tipo 1 — sensibles al contexto, por autómatas linealmente acotados.
• Tipo 0 — recursivamente enumerables, por máquinas de Turing.

Cada clase contiene estrictamente a la anterior. El curso recorrió la jerarquía de arriba hacia abajo: empezamos en el tipo 0 y llegamos aquí. Ahora ya sabes exactamente qué separa cada nivel del siguiente y por qué.

CLAUSURA

Los libres de contexto son cerrados bajo unión, concatenación y estrella, pero no bajo intersección ni complemento. El contraejemplo: {aⁿbⁿcᵐ} ∩ {aᵐbⁿcⁿ} = {aⁿbⁿcⁿ}, que no es libre de contexto.

EJERCICIO

Convertir una gramática a autómata de pila y verificar el reconocimiento de tres cadenas paso a paso.