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ý).

 

Bezkontextová gramatika G, může být chápána jako čtveřice <math>G = (\Pi\,, \Sigma\,, P\,, S\,)</math>, kde

 

** β 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]] -->

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:

== Externí odkazy ==

 

* [http://www1.osu.cz/home/habibal/publ/rabj2.pdf Regulární a bezkontextové jazyky II.]