Kontextová gramatika

z Wikipédie, slobodnej encyklopédie
Skočit na navigaci Skočit na vyhledávání

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

αAβ → αγβ

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

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.