Gramáticas sensibles al contexto

Una gramática sensible al contexto es una gramática formal que se define como una cuádrupla G = (N, Σ, P, S) en donde:

En este tipo de gramáticas, las producciones son de la forma α → β, donde α y β no permiten ε de una producción, es decir, no se permite la palabra vacía tanto para el lado izquierdo como para el lado derecho.

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.

Un lenguaje formal que puede ser descrito para una gramática sensible al contexto se llama lenguaje sensible al contexto.

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 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 sensible al contexto está contenida en las de longitud creciente y viceversa.