Kontextová gramatika

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Kontextová gramatika je formální gramatika G = (N, Σ, P, S), ve které jsou pravidla v P tvaru

αAβ → αγβ

kde AN (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 a zároveň ε ∈ Σ, 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říklad[editovat | editovat zdroj]

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 \{ a^n b^n c^n : n \ge 1 \} , 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á nesmí měnit terminál na nonterminál. Tedy správně má být (bez záruky):

S → abC | aSBC
CB → XB
XB → XC
XC → BC
bB → bb
bC → bc
cC → cc

Vlastnosti[editovat | editovat zdroj]

Problém, zda daný řetězec s náleží do jazyka dané gramatiky G, je PSPACE úplný.