Una gramática sensible al contexto ( CSG ) es una gramática formal en la que los lados izquierdo y derecho de cualquier regla de producción pueden estar rodeados por un contexto de símbolos terminales y no terminales . Las gramáticas sensibles al contexto son más generales que las gramáticas libres de contexto , en el sentido de que hay lenguajes que pueden ser descritos por CSG pero no por gramáticas libres de contexto. Las gramáticas sensibles al contexto son menos generales (en el mismo sentido) que las gramáticas no restringidas . Así, las CSG se posicionan entre las gramáticas sin contexto y sin restricciones en la jerarquía de Chomsky . [1]
Un lenguaje formal que puede describirse mediante una gramática sensible al contexto o, de manera equivalente, mediante una gramática no contratante o un autómata lineal acotado , se denomina lenguaje sensible al contexto . Algunos libros de texto definen a los CSG como no contractuales, [2] [3] [4] [5] aunque no es así como los definió Noam Chomsky en 1959. [6] [7] Esta elección de definición no hace ninguna diferencia en términos de los idiomas generados (es decir, las dos definiciones son débilmente equivalentes )), pero sí hace una diferencia en términos de qué gramáticas se consideran estructuralmente sensibles al contexto; este último tema fue analizado por Chomsky en 1963. [8] [9]
Chomsky introdujo las gramáticas sensibles al contexto como una forma de describir la sintaxis del lenguaje natural donde a menudo ocurre que una palabra puede o no ser apropiada en un lugar determinado según el contexto. Walter Savitch ha criticado la terminología "sensible al contexto" por ser engañosa y ha propuesto que "no borrado" explica mejor la distinción entre un CSG y una gramática sin restricciones . [10]
Aunque es bien sabido que ciertas características de los lenguajes (por ejemplo , la dependencia entre series ) no están libres de contexto, es una pregunta abierta cuánto del poder expresivo de CSG se necesita para capturar la sensibilidad del contexto que se encuentra en los lenguajes naturales. La investigación posterior en esta área se ha centrado en los lenguajes ligeramente sensibles al contexto más manejables desde el punto de vista computacional . [ cita requerida ] Las sintaxis de algunos lenguajes de programación visual pueden describirse mediante gramáticas gráficas sensibles al contexto . [11]
Una gramática formal G = ( N , Σ, P , S ), con N un conjunto de símbolos no terminales, Σ un conjunto de símbolos terminales, P un conjunto de reglas de producción y S el símbolo de inicio , es sensible al contexto si todas las reglas en P son de la forma
Una cadena u ∈ ( N ∪Σ) * produce directamente , o se deriva directamente de , una cadena v ∈ ( N ∪Σ) * , denotada como u ⇒ v , si u puede escribirse como l α A β r , y v puede escribirse como l αγβ r , para alguna regla de producción (α A β→αγβ) ∈ P , y algunas cadenas de contexto l , r ∈ ( N ∪Σ) * . Más generalmente,Se dice que u da , o deriva a , v , denotada como u ⇒ * v , si u = u 1 ⇒ ... ⇒ u n = v para algún n ≥0 y algunas cadenas u 2 , ..., u n -1 ( norte ∪Σ ) * . Es decir, la relación (⇒ * ) es la clausura reflexiva transitiva de la relación (⇒).