text: # 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říklad
  Následující kontextová gramatika generuje jazyk{\displaystyle \{a^{n}b^{n}c^{n}:n\geq 1\}}, o němž lze pomocí pumping lemmatu pro bezkontextové jazyky dokázat, že není bezkontextový:
  S → abC
  S → aSBC
  CB → XB
  XB → XY
  XY → XC
  XC → BC
  bB → bb
  bC → bc
  cC → cc
  Gramatiku lze snáze zapsat jako monotonní (vyjadřovací síla monotonních gramatik je stejná jako bezkontextových):
  S → abc
  S → aSBc
  cB → Bc
  bB → bb
  
  ## Vlastnosti
  Problém, zda daný řetězec s náleží do jazyka generovaného danou kontextovou gramatikou G, je PSPACE-úplný.
  
title: Kontextová gramatika
wikitext: '''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'' ∪ Σ)<sup>+</sup> (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 (lingvistika)|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á gramatika|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 [[Jazyk (lingvistika)|jazyka]], ve kterém lze určité slovo použít právě v závislosti na okolním kontextu.
  
  == Příklad ==
  Následující kontextová gramatika generuje jazyk<math> \{ a^n b^n c^n : n \ge 1 \} </math>, o němž lze pomocí [[Lemma o vkládání#Lemma o vkládání pro bezkontextové jazyky|pumping lemmatu pro bezkontextové jazyky]] dokázat, že není bezkontextový:
  :S → abC
  :S → aSBC
  :CB → XB
  :XB → XY
  :XY → XC
  :XC → BC
  :bB → bb
  :bC → bc
  :cC → cc
  
  Gramatiku lze snáze zapsat jako [[Monotonní gramatika|monotonní]] (vyjadřovací síla monotonních gramatik je stejná jako bezkontextových):
  :S → abc
  :S → aSBc
  :cB → Bc
  :bB → bb
  
  == Vlastnosti ==
  Problém, zda daný řetězec ''s'' náleží do jazyka generovaného danou kontextovou gramatikou ''G'', je [[PSPACE-úplný]].
  
  == Odkazy ==
  === Související články ===
  * [[Formální gramatika]]
  * [[Monotonní gramatika]]
  * [[Chomského hierarchie]]
  
  {{Formální jazyky a gramatiky}}
  {{Autoritní data}}
  
  [[Kategorie:Formální jazyky]]
  [[Kategorie:Gramatické modely]]
infoboxes: []