Bezkontextová gramatika: Porovnání verzí

V [[lingvistika|lingvistice]] a [[informatika|informatice]] označuje pojem '''bezkontextová gramatika''' ('''CFG''') [[formální gramatika|formální gramatiku]], ve které mají všechna přepisovací pravidla tvar

kde A je neterminál a β je řetězec terminálů a/nebo neterminálů. Název „bezkontextová“ vychází ze skutečnosti, že neterminál se může přepsat na β bez ohledu na okolní [[kontext]]. Jazyky generované bezkontextovými gramatikami se nazývají [[bezkontextový jazyk|bezkontextové]]. Bezkontextová gramatika je speciálním případem [[kontextová gramatika|gramatiky kontextové]] (kontext je prázdný).

 

== Formální definice ==

 

terminálů.

 

* Σ je konečná množina terminálů, kde průnik množin Π∩Σ = ø

* S je počáteční proměnná, která patří do množiny Π neterminálů,

** A je neterminál, A ∈ Π

** β je řetězec složený z terminálů a neterminálů, β ∈ (Π ∪ Σ)*.

Jednoduchá bezkontextová gramatika je dána přepisovacím pravidlem:

 

 

kde znak | separuje více možností řetězců (w) z terminálů a neterminálů, které znamenají to samé jako zápis:

 

kde a, b označuje terminály, S je startovní symbol (neterminál). Tato gramatika generuje jazyk a^n b^n, kde n>=1. Tento jazyk není regulární. Speciální symbol ε označuje prázdný řetězec. Pokud změníme pravidlo na S → aSb | ε získáme gramatiku, která generuje jazyk a^n b^n, kde n>=0. Tato přepisovací pravidlo obsahuje i přepis na prázdný řetězec, který původní gramatika neobsahuje.

Tato bezkontextová gramatika generuje aritmetické výrazy s proměnnými ''x'', ''y'', ''z'':

 

 

S touto gramatikou dokážeme například generovat řetězec "( x + y ) * x - z * y / ( x + x )". Tento řetězec získáme následujícím postupem. Startovací symbol S přepíšeme podle páté transformace [S → S - S]. Následně se S na pravé straně přepíší podle šesté a sedmé transformace na řetězec "S * S - S / S", pak použijeme poslední transformaci s uzávorkováním, tak získáme "( S ) * S - S / ( S )". Poté uzávorkovaná S přepíšeme podle transformace [S → S + S]. Takto dostanem řetězec neterminálů "( S + S ) * S - S * S / ( S + S )", z kterého výsledný řetězec "( x + y ) * x - z * y / ( x + x )" získáme převedením neterminálů S na terminály x, y, z.

Bezkontextová gramatika, která se skládá ze slov obsahující znaky a, b v různém počtu a pořadí.

 

 

Neterminál T dovoluje generovat všechny řetězce se stejným počtem áček a béček. Neterminál U generuje řetězec s větším počtem áček než béček. Poslední neterminál V generuje řetězec s větším počtem béček než áček.

Dalším příkladem je bezkontextová gramatika, která generuje jazyk {b^n, a^n, 2*b^n, kde a>=0, b>=0}. Toto není regulární jazyk, ale je bezkontextový a může být generován bezkontextovou gramatikou:

 

 

=== Derivace a syntaktický strom ===<!-- This section is linked from [[LR parser]] -->

Je několik způsobů jak získat potřebný řetězec. Jedním ze způsobů jak jej získat je derivování od startovního symbolu pomocí dané gramatiky. Nejjednodušší cestou je výpis mezikroků od startovního symbolu až po výsledný řetězec a k tomu výpis použitých přepisovacích pravidel. Pokud použijeme strategii, ve které vždy nejprve nahradíme nejlevější neterminál, pak pro kontextovou gramatiku je seznam pravidel použité gramatiky dostačující. Toto nazýváme „levou derivací“ řetězce. Například pokud vezmeme tuto gramatiku:

 

 

a řetězec "1 + 1 + a", pak levá derivace tohoto řetězce bude posloupnost použitých pravidel [ (1), (1), (2), (2), (3) ]. Analogicky u pravé derivace se vždy nejprve nahradí nejpravější neterminál. V tomto případě bude seznam pravidel v následujícím pořadí [ (1), (3), (1), (2), (2)].

Pomocí derivace uložíme hierarchickou strukturu v řetězci, který je derivován. Jako příklad poslouží řetězec "1 + 1 + a", který je derivován podle levé derivace:

 

 

řetězcová struktura může vypadat následovně:

Tento strom se nazývá ''konkrétní syntaktický strom'' (nebo také [[abstraktní syntaktický strom]]) řetězce. V tomto případě levá a pravá derivace definuje stejný syntaktický strom. U tohoto řetězce můžeme pomocí levé derivace získat jinou stromovou strukturu a to záměnou prováděných přepisovacích pravidel:

 

 

ta definuje následný syntaktický strom:

 

== Normální formy ==

 

Pro jednoduchost vytváření pravidel je Chomského normální forma vhodná jak pro teoretickou, tak pro praktickou realizaci. Pro případ bezkontextové gramatiky, která používá Chomského normální formu pro konstrukci časově polynomicky náročného algoritmu, kde se rozhoduje zda daný řetězec je v jazyce reprezentovaným gramatikou nebo není ([[CYK algoritmus]]).