Kontextová gramatika

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

αAβ → αγβ

s A ∈ N (t. j., A je jeden neterminálny symbol) a α a β ∈ (N ∪ Σ)* (t. j., α a β sú reťazce neterminálnych a terminálnych symbolov) a γ ∈ (N ∪ Σ)⁺ (t. j., γ je neprázdny reťazec neterminálnych a terminálnych symbolov). Ak sa S nevyskytuje na pravej strane žiadneho pravidla, môže gramatika obsahovať i pravidlo

S → ε

kde ε značí prázdny reťazec.

Ďalej platí, že dĺžka ľavej strany každého pravidla musí byť menšia alebo rovná dĺžke pravej strany daného pravidla.

Názov kontextová je odvodený od faktu, že α a β tvoria kontext, ktorý určuje, či A je možné nahradiť γ alebo nie. Týmto sa odlišuje od bezkontextovej gramatiky, kde sa kontext neterminálneho 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.