Kontextová gramatika
Kontextová gramatika je formální gramatika G = (N, Σ, P, S), ve které jsou pravidla v P tvaru
- αAβ → αγβ
kde A ∈ N (to znamená, že A je jeden neterminál) a α, β ∈ (N ∪ Σ)* (to znamená, že α a β jsou řetězce neterminálů a terminálů) a γ ∈ (N ∪ Σ)+ (to znamená, že γ je neprázdný řetězec terminálů a neterminálů). Pokud se S nevyskytuje na pravé straně žádného pravidla, může gramatika obsahovat i pravidlo
- S → ε
kde ε značí prázdný řetězec.
Název kontextová je odvozen od faktu, že α a β tvoří kontext, který určuje, zda A lze přepsat na γ. Speciálním případem kontextové gramatiky je gramatika, u které kontext nehraje roli (α i β jsou ve všech pravidlech prázdné). Taková gramatika se označuje jako bezkontextová, bezkontextové gramatiky jsou tedy podmnožinou kontextových gramatik. Formální jazyk popsaný kontextovou gramatikou se nazývá kontextový jazyk.
S myšlenkou kontextových gramatik přišel Noam Chomsky ve snaze popsat syntax přirozeného jazyka, ve kterém lze určité slovo použít právě v závislosti na okolním kontextu.
PříkladEditovat
Jednoduchá gramatika je například
- S → abc | aSBc
- cB → Bc
- bB → bb
kde | je označení pro různé možnosti přepisu jednoho neterminálu. Tato gramatika generuje jazyk , který není bezkontextový.
Pozor! Uvedená gramatika není kontextová (neodpovídá výše uvedenému předpisu). Třetí pravidlo (druhý řádek) musí být rozepsáno pomocí následujícího:
- AB → BA převedeme na
- AB → XB
- XB → XA
- XA → BA
Pozor! Další chyba. Kontextová gramatika nesmí měnit terminál na neterminál. Tedy správně má být:
- S → abC | aSBC
- CB → XB
- XB → XY
- XY → XC
- XC → BC
- bB → bb
- bC → bc
- cC → cc
VlastnostiEditovat
Problém, zda daný řetězec s náleží do jazyka dané gramatiky G, je PSPACE úplný.