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

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

Gramáticas libres de contexto

SUBIR UN NIVEL

Los autómatas finitos no pueden contar sin cota. Las gramáticas libres de contexto sí, porque generan estructura anidada. Son el modelo de la sintaxis de los lenguajes de programación.

GENERAR EN VEZ DE RECONOCER

Una gramática no acepta cadenas: las produce. Se parte de un símbolo y se aplican reglas de sustitución hasta obtener una cadena de terminales.

DEFINICIÓN FORMAL

G = (V, T, P, S).

• V — variables o símbolos no terminales.
• T — terminales, el alfabeto del lenguaje generado.
• P — producciones de la forma A → α, con A ∈ V y α ∈ (V ∪ T)*.
• S ∈ V — símbolo inicial.

QUÉ SIGNIFICA LIBRE DE CONTEXTO

El lado izquierdo de toda producción es una sola variable. A puede reemplazarse por α sin importar qué haya alrededor: el contexto no condiciona. De ahí el nombre.

DERIVACIÓN

• Un paso: αAβ ⇒ αγβ si A → γ está en P.
• L(G) = {w ∈ T* | S ⇒* w}.
• Derivación por la izquierda: se expande siempre la variable más a la izquierda. Por la derecha, la más a la derecha.

EJEMPLOS

S → 0S1 | ε genera {0ⁿ1ⁿ}, que acabamos de demostrar que no es regular. Con una sola producción recursiva se supera todo lo que puede hacer un autómata finito.

S → (S) | SS | ε genera los paréntesis balanceados.

E → E+E | E*E | (E) | id genera expresiones aritméticas.

RECURSIÓN, OTRA VEZ

Una gramática es una definición recursiva de un conjunto de cadenas. Es la cuarta vez en el curso que aparece la misma idea, y no es coincidencia: la recursión es el mecanismo que produce infinitud a partir de reglas finitas.

NOTACIÓN BNF

Las gramáticas de lenguajes reales se escriben en Backus-Naur o su versión extendida. Es la misma idea con otra sintaxis, y es como vienen las especificaciones oficiales de C, Java o Python.

EJERCICIO

Escribir gramáticas para: palíndromos; cadenas con igual número de a y b; aⁿbᵐ con n > m; comentarios anidados.