- S es el símbolo distinguido o axioma
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.