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 $G=(V,\Sigma ,R,S)$, waarbij

$V\,$ een verzameling niet-terminale symbolen of variabelen is;

$\Sigma \,$ een verzameling terminale symbolen, waarbij $V\cap \Sigma =\emptyset$;

$R\,$ een verzameling productieregels van de vorm $l\to r$, waarbij $l,r\in (V\cup \Sigma )^{*}$ en $1\leq |l|\leq |r|$ (als uitzondering mag de productieregel $S\to \epsilon$ voorkomen, maar alleen als $S$ in geen enkele productieregel in de rechterkant voorkomt); en

$S\in V$ 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 $G=(V,\Sigma ,R,S)$, met $V=\{S,B,C\}$ en $\Sigma =\{a,b,c\}$, die uit de volgende productieregels bestaat:

• $S\to aSBC$
• $S\to aBC$
• $CB\to BC$
• $aB\to ab$
• $bB\to bb$
• $bC\to bc$
• $cC\to cc$

Deze grammatica genereert de niet-contextvrije taal $\{a^{n}b^{n}c^{n}\mid n>0\}$.

Literatuur

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