Kontextová gramatika

Kontextová gramatika je formální gramatika G = (N, Σ, P, S), ve které jsou pravidla v P tvaru

αAβ → αγβ

kde A ∈ N (to znamená, že A je jeden neterminál) a α, β ∈ (N ∪ Σ)* (to znamená, že α a β jsou řetězce neterminálů a terminálů) a γ ∈ (N ∪ Σ)⁺ (to znamená, že γ je neprázdný řetězec terminálů a neterminálů). Pokud se S nevyskytuje na pravé straně žádného pravidla, může gramatika obsahovat i pravidlo

S → ε

kde ε značí prázdný řetězec.

Název kontextová je odvozen od faktu, že α a β tvoří kontext, který určuje, zda A lze přepsat na γ. Speciálním případem kontextové gramatiky je gramatika, u které kontext nehraje roli (α i β jsou ve všech pravidlech prázdné). Taková gramatika se označuje jako bezkontextová, bezkontextové gramatiky jsou tedy podmnožinou kontextových gramatik. Formální jazyk popsaný kontextovou gramatikou se nazývá kontextový jazyk.

S myšlenkou kontextových gramatik přišel Noam Chomsky ve snaze popsat syntax přirozeného jazyka, ve kterém lze určité slovo použít právě v závislosti na okolním kontextu.

Následující kontextová gramatika generuje jazyk${\displaystyle \{a^{n}b^{n}c^{n}:n\geq 1\}}$, o němž lze pomocí pumping lemmatu pro bezkontextové jazyky dokázat, že není bezkontextový:

S → abC

S → aSBC

CB → XB

XB → XY

XY → XC

XC → BC

bB → bb

bC → bc

cC → cc

Gramatiku lze snáze zapsat jako monotonní (vyjadřovací síla monotonních gramatik je stejná jako bezkontextových):

S → abc

S → aSBc

cB → Bc

bB → bb

Problém, zda daný řetězec s náleží do jazyka generovaného danou kontextovou gramatikou G, je PSPACE-úplný.

• Formální gramatika
• Monotonní gramatika
• Chomského hierarchie