Kontextová gramatika

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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

αAβ → αγβ

s AN (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.

Formálne jazyky, automaty a gramatiky
Chomského
hierarchia
Gramatiky Jazyky Minimálny
automat
Typ-0 Frázová Rekurzívne vyčísliteľný Turingov stroj
Rekurzívny Vždy zastavujúci Turingov stroj
Typ-1 Kontextová Kontextový (Nedeterministický) lineárne ohraničený
Typ-2 Bezkontextová Bezkontextový (Nedeterministický) zásobníkový
Typ-3 Regulárna Regulárny Konečný
Každá množina jazykov alebo gramatík je vlastnou nadmnožinou množiny priamo pod ňou.