Gramática
sensible al contexto: una gramática sensible al contexto es una gramática sin restricciones en la que todas las producciones son de forma, 
donde α y β son strings de no terminales y terminales.
Las gramáticas sensibles al contexto son más poderosas que las gramáticas libres de contexto porque hay algunos lenguajes que pueden ser descritos por CSG pero no por gramáticas libres de contexto y CSL son menos poderosas que la gramática no restringida. Es por eso que las gramáticas sensibles al contexto se ubican entre las gramáticas sin contexto y sin restricciones en la jerarquía de Chomsky.
La gramática sensible al contexto tiene 4 tuplas. G = {N, Σ, P, S} , Donde
N = Conjunto de símbolos no terminales
Σ = Conjunto de símbolos terminales
S = Símbolo de inicio de la producción
P = Conjunto finito de producciones
Todas las reglas en P son de la forma α 1 A α 2 –> α 1 β α 2
Lenguaje sensible al contexto: El lenguaje que se puede definir mediante la gramática sensible al contexto se llama CSL. Las propiedades de CSL son:
- La unión, intersección y concatenación de dos lenguajes sensibles al contexto es sensible al contexto.
- El complemento de un lenguaje sensible al contexto es sensible al contexto.
Ejemplo –
Considere el siguiente CSG.
S → abc/aAbc
Ab → bA
Ac → Bbcc
bB → Bb
aB → aa/aaA
¿Cuál es el lenguaje generado por esta gramática?
Solución :
S → aAbc
→ abAc
→ abBbcc
→ aBbbcc
→ aaAbbcc
→ aabAbcc
→ aabbAcc
→ aabbBbccc
→ aabBbbccc
→ aaBbbbccc
→ aaabbbccc
El lenguaje generado por esta gramática es { a n b n c n | n≥1}.
Preguntas de GATE CS Corner
Practicar las siguientes preguntas te ayudará a poner a prueba tus conocimientos. Todas las preguntas se han hecho en GATE en años anteriores o en pruebas simuladas de GATE. Es muy recomendable que los practiques.
Referencias –
CSG – Wikipedia
CSG – csa.iisc.ernet.in