Kontextovo citlivá gramatika
Z Wikipédie
Kontextovo citlivá gramatika alebo kontextovo závislá 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ý nekoncový symbol) a α a β ∈ (N ∪ Σ)* (t.j., α a β reťazce nekoncových symbolov a koncových symbolov) a γ ∈ (N ∪ Σ)+ (t.j., γ neprázdny reťazec nekoncových a koncových symbolov), 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 kontextovo citlivá 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 kontextovo citlivej 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.
