Gramáticas sensibles al contexto

Una gramática sensible al contexto es una gramática formal G = (N, Σ, P, S) tal que todas las producciones P son de la forma:

αAβ → αγβ

con A en N y α y β en (N U Σ)* y γ en (N U Σ)⁺, con la posibilidad de la regla lambda

S → λ

con λ, la cadena vacía.

Se lo llama sensible al contexto porque α y β determinan la forma que debe tener una cadena que puede ser reemplazada por alguna de las producciones. Una lenguaje formal que puede ser descripto para una gramática sensible al contexto se llama lenguaje sensible al contexto

Definición alternativa

Otra forma de definir las gramáticas sensibles al contexto, es aquella gramática formal con la única restricción que todas las producciones α -> β en P cumplan que |α| ≤ |β| donde |α| es la longitud de α. Se las llama de longitud no decreciente.

Se demuestra que las gramáticas sensibles al contexto, y las de longitud creciente son equivalentes en el sentido que generan los mismos lenguajes, a través de una doble contención, es decir, toda gramática libre de contexto está contenida en las de longitud creciente y viceversa.

Ejemplo

S → abc | aSBc

cB → Bc

bB → bb

Esta gramática genera este lenguaje: $\{ a^n b^n c^n : n \ge 1 \}$, que no es libre de contexto. Esto lo sabemos gracias al lema del bombeo. También existe una gramática sensible al contexto para $\{ a^n b^n c^n d^n : n \ge 1 \}$, pero es mucho más compleja que la anterior