Kontextová gramatika

Kontextová gramatika je formálna gramatika G = (N, Σ, P, S), kde všetky pravidlá v P sú tvaru

αAβ → αγβ

s A ∈ N (t. j., A je jediný neterminálny symbol) a α a β ∈ (N ∪ Σ)* (t. j., α a β reťazce neterminálnych symbolov a terminálnych symbolov) a γ ∈ (N ∪ Σ)⁺ (t. j., γ neprázdny reťazec neterminálov a terminálov), plus pravidlo tvaru

S → ε

Ďalej platí, že dĺžka ľavej strany každého pravidla musí byť menšia alebo rovná dĺžke pravej strany daného pravidla. s ε prázdny reťazec, je povolené, ak sa S nevyskytuje na pravej strane žiadneho z pravidiel.

Názov kontextová je vysvetlený tým, že α a β tvoria kontext A a určujú, či A je možné nahradiť γ alebo nie. Týmto sa odlišuje od bezkontextovej gramatiky, kde sa kontext nekoncového symbolu neberie do úvahy. Formálny jazyk, ktorý je možné opísať kontextovo citlivou gramatikou sa nazýva kontextovo citlivý jazyk.

Koncept kontextovej gramatiky zaviedol Noam Chomsky v 50. rokoch 20. storočia ako spôsob opisu syntaxe prirodzených jazykov, kde je skutočne častým javom, že slovo môže alebo nemusí byť vhodné na danom mieste v závislosti na kontexte.