Contextgevoelige grammatica
Een contextgevoelige grammatica, soms ook contextsensitieve grammatica genoemd, is een formele grammatica waarin voor alle productieregels geldt dat de lengte van het linker deel kleiner of gelijk is aan de lengte van het rechter deel. Deze voorwaarde zorgt ervoor dat het beslisbaar is of een gegeven woord door een contextgevoelige grammatica kan worden gegenereerd.

Definitie 
Een contextgevoelige grammatica is is een grammatica , waarbij
 een verzameling niet-terminale symbolen of variabelen is;
 een verzameling terminale symbolen, waarbij ;
 een verzameling productieregels van de vorm , waarbij  en  (als uitzondering mag de productieregel  voorkomen, maar alleen als  in geen enkele productieregel in de rechterkant voorkomt); en
 de startvariabele.
Een taal L heet contextgevoelig als ze door een contextgevoelige grammatica wordt gegenereerd. De contextgevoelige talen vormen de type-1-talen in de Chomskyhiërarchie.

Woordprobleem 
Voor contextgevoelige grammatica's is het woordprobleem beslisbaar. Dat wil zeggen, er bestaat een algoritme dat, gegeven een woord w en een contextgevoelige grammatica G, beslist of w door G kan worden gegenereerd. Bij elke afleidingsstap wordt het tot nu toe gevormde woord namelijk langer of blijft het even lang. Daardoor kan het zoeken naar een afleiding van w worden afgebroken als het tot nu toe gevormde woord langer is dan w, en blijft er een eindige zoekboom over, die brute-force doorzocht kan worden. Er bestaan echter, in tegenstelling tot contextvrije grammatica's, geen efficiënte algoritmes om het woordprobleem op te lossen.

Voorbeeld 
Een voorbeeld van een contextgevoelige grammatica is de grammatica , met  en , die uit de volgende productieregels bestaat:
 
 
 
 
 
 
 
Deze grammatica genereert de niet-contextvrije taal .

Literatuur 
  Uwe Schöning. Theoretische Informatik Kurzgefasst. 5e druk. Spektrum, 2008
  John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to automata theory, languages and computation, 2nd edition. Addison-Wesley, 2001

Formele taal