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: * N es un alfabeto de símbolo no terminales (variables) * Σ es un alfabeto de símbolos terminales con N ∩ Σ = ∅ * S ∈ N es el símbolo inicial * P es el conjunto finito de producciones de la forma α → β, donde α y β ∈ (N ∪ Σ)+ y |α| ≤ |β|. En este tipo de gramáticas, las producciones son de la forma α → β, donde α y β no permiten ε de una producción, es decir, nose permite la palabra vacía tanto para el lado izquierdo como para el lado derecho. Sin embargo, pueden contener cualquier cantidad de variables (no terminales) y constantes (terminales). 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.