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

NE111 · miércoles 04/11/2026 · 16:00-17:15 · Sesión 25

Evaluación de gramáticas · Simplificación y formas normales

POR QUÉ SIMPLIFICAR

Los algoritmos sobre gramáticas —decidir pertenencia, convertir a autómata de pila, aplicar el lema del bombeo— suponen una forma estándar. Simplificar es el paso previo obligatorio.

ELIMINACIÓN DE SÍMBOLOS INÚTILES

• No generadores — variables desde las que no se deriva ninguna cadena de terminales.
• No alcanzables — variables a las que nunca se llega desde S.

El orden importa: primero los no generadores y después los no alcanzables. Al revés pueden quedar símbolos inútiles.

ELIMINACIÓN DE PRODUCCIONES Ε

1. Hallar las variables anulables, las que derivan ε directa o indirectamente.

2. Por cada producción, agregar las versiones con subconjuntos de anulables borrados.

3. Eliminar las producciones A → ε, salvo S → ε si ε pertenece al lenguaje.

ELIMINACIÓN DE PRODUCCIONES UNITARIAS

Las de la forma A → B no aportan estructura. Se calculan los pares unitarios y se sustituye cada A → B por las producciones no unitarias de B.

FORMA NORMAL DE CHOMSKY

Toda producción es A → BC o A → a, salvo posiblemente S → ε. El árbol de derivación queda binario, y una cadena de longitud n se deriva en exactamente 2n − 1 pasos.

EL ALGORITMO CYK

Con la gramática en forma normal de Chomsky, decide si una cadena pertenece al lenguaje en O(n³) mediante programación dinámica: llena una tabla triangular con las variables que generan cada subcadena.

Es la evaluación de una gramática hecha algoritmo, y conecta con la complejidad del segundo bloque: pertenencia a un lenguaje libre de contexto está en P.

FORMA NORMAL DE GREIBACH

Toda producción es A → aα, con un terminal al inicio. Garantiza que cada paso consume un símbolo, lo que hace directa la conversión a autómata de pila y evita ciclos infinitos en el análisis descendente.

EJERCICIO

Simplificar una gramática, convertirla a forma normal de Chomsky y aplicar CYK a una cadena de cinco símbolos.