Gramáticas Sensibles al Contexto

Gramáticas
Las gramáticas formales definen un lenguaje describiendo cómo se pueden generar las cadenas del lenguaje.
Una gramática formal es una cuadrupla G = (N, T, P, S) donde
    - N es un conjunto finito de símbolos no terminales
    - T es un conjunto finito de símbolos terminales 
   -  P es un conjunto finito de producciones
       Cada producción de P tiene la forma
    - S es el símbolo distinguido o axioma 
Restringiendo los formatos de producciones permitidas en una gramática, se pueden especificar cuatro tipos de gramáticas (tipo 0, 1, 2 y 3) y sus correspondientes clases de lenguajes.

Gramáticas sensibles al contexto (Tipo 1)
Las gramáticas sensibles al contexto o de tipo 1, son las que generan los lenguajes sensibles al contexto. Los lenguajes sensibles al contexto son aquellos que pueden ser reconocidos por las Autómatas Linealmente Acotados ALA.
En forma general toda gramática se define mediante una cuádrupla G=(N,T, P,S), siendo
    -N es un conjunto finito de símbolos no terminales
    -T es un conjunto finito de símbolos terminales 
    -P es un conjunto finito de reglas de producción
    -S Símbolo distinguido o Axioma 
En una gramática sensible al contexto, cada regla de producción de P tiene la forma

Es decir, se permite el reemplazo del no terminal A en el lado izquierdo de la producción, por la cadena sólo en el "contexto" .  La gramática puede contener también la producción , si el lenguaje que se quiere generar contiene la cadena vacía.