Zobrazení zdroje stránky Bezkontextová gramatika

V [[lingvistika|lingvistice]] a [[informatika|informatice]] označuje pojem '''bezkontextová gramatika''' ({{Vjazyce2|en|''Context-free Grammar'', ''CFG''}}) [[formální gramatika|formální gramatiku]], ve které mají všechna přepisovací pravidla tvar
: ''A'' → ''β''
kde ''A'' je neterminál a ''β'' je řetězec složený z terminálů a/nebo neterminálů. Název „bezkontextová“ (u některých autorů „nekontextová“) vychází ze skutečnosti, že neterminál se může přepsat bez ohledu na okolní [[kontext]]. Bezkontextová gramatika je speciálním případem [[kontextová gramatika|gramatiky kontextové]] (kontext je prázdný). Jazyky generované bezkontextovými gramatikami se nazývají [[bezkontextový jazyk|bezkontextové]].

== Termíny ==
'''Bezkontextová gramatika''' je určena konečnou množinou '''neterminálů''' ('''[[Neterminální symbol|neterminálních symbolů]]''' - proměnných), konečnou množinou '''terminálů''' ('''[[Terminální symbol|terminálních symbolů]]'''), která nemá společné prvky s množinou neterminálů, '''počátečním neterminálem''' S a konečnou množinou '''přepisovacích pravidel''' tvaru ''A'' → ''β'', (''A'' přepiš na ''β''), kde ''A'' je neterminál a ''β'' je řetězec z neterminálů a terminálů.

{{Kotva|Přepsání}}'''Přepsání''' je operace, při které se v řetězci složeném z terminálů a neterminálů nahradí podřetězec tvořící levou stranu nějakého pravidla gramatiky pravou stranou tohoto pravidla. Někdy se používá termín '''bezprostřední přepsání''' pro zdůraznění, že se jedná o jedno použití přepisovacího pravidla.

{{Kotva|Odvození}}{{Kotva|Derivace}}'''Odvození''' neboli '''derivace''' je postup, při kterém se na řetězec uplatní konečný počet (žádné, jedno nebo více) přepsání.

{{Kotva|Větná forma}}'''Větná forma''' ({{Vjazyce2|en|''sentential form''}}) určité gramatiky je libovolný řetězec složený z terminálů a neterminálů, který lze získat z počátečního symbolu konečným počtem přepsání.

{{Kotva|Řetězec generovaný gramatikou}}'''Řetězec generovaný''' danou '''gramatikou''', méně formálně '''věta gramatiky''' je větná forma, která je tvořena pouze terminálními symboly.

{{Kotva|Jazyk generovaný gramatikou}}'''Jazyk generovaný gramatikou''' je množina všech řetězců, generovaných gramatikou.

{{Kotva|Levá derivace}}'''Levá derivace''' neboli '''levé odvození''' ({{Vjazyce2|en|''leftmost derivation''}}) je takový postup při generování určitého slova v bezkontextové gramatice, že se vždy přepisuje první neterminální symbol zleva. Bezkontextovost gramatiky umožňuje přepisovat neterminály v libovolném pořadí.

{{Kotva|Pravá derivace}}'''Pravá derivace''' neboli '''pravé odvození''' ({{Vjazyce2|en|''rightmost derivation''}}) je takový postup při generování určitého slova v bezkontextové gramatice, že se vždy přepisuje poslední neterminální symbol (tj. první zprava).

== Formální definice ==
Bezkontextová gramatika<ref>{{Citace monografie
| příjmení = Molnár
| jméno = Ľudovít
| příjmení2 = Češka
| jméno2 = Milan
| příjmení3 = Melichar
| jméno3 = Bořivoj
| titul = Gramatiky a jazyky
| vydavatel = Alfa
| místo = Bratislava
| rok = 1987
| vydání = 3
}}</ref> je čtveřice ''G'' = (''V''<sub>N</sub>, ''V''<sub>T</sub>, ''P'', ''S''), kde

* ''V''<sub>N</sub> je konečná množina '''neterminálních symbolů''', krátce '''neterminálů''',
* ''V''<sub>T</sub> je konečná množina '''terminálních symbolů''', krátce '''terminálů''', přičemž tyto dvě množiny nemají žádné společné prvky (''V<sub>T</sub>'' ∩ ''V''<sub>N</sub> = ø)
* ''P'' je konečná množina '''přepisovacích pravidel''' tvaru ''A'' → ''β'', kde
** ''A'' je neterminál, ''A'' ∈ ''V''<sub>N</sub>
** ''β'' je řetězec složený z terminálů a neterminálů, β ∈ (''V''<sub>N</sub> ∪ ''V''<sub>T</sub>)*.
* ''S'' je '''počáteční symbol''', který patří do množiny ''V''<sub>N</sub> neterminálů.

Přepsání ''αAγ'' ⊨ ''αβγ'' je nahrazení řetězce ''αAγ'' řetězcem ''αβγ'', kde ''A'' → ''β'' je pravidlo gramatiky a ''α'',''γ'' ∈ (''V''<sub>N</sub> ∪ ''V''<sub>T</sub>)*.

Derivace ⊨<sup>*</sup> je tranzitivní a reflexívní uzávěr přepsání.

Jazyk generovaný gramatikou ''G'' je ''L''(''G'') = { ''w'' | ''w'' ∈ ''V''<sub>T</sub><sup>*</sup> & ''S'' ⊨<sup>*</sup> ''w'' }.

== Příklady ==

=== Příklad 1 ===
Jednoduchá bezkontextová gramatika je dána přepisovacím pravidlem:

: S → aSb | ab (stejně jako A → β)

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

: S → aSb
: S → ab
 
kde a, b označuje terminály, S je startovní symbol (neterminál). Tato gramatika generuje jazyk a<sup>n</sup>b<sup>n</sup>, kde <math>n \geq 1</math>. Tento jazyk není [[Regulární jazyk|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<sup>n</sup>b<sup>n</sup>, kde <math>n \geq 0</math>. Tato přepisovací pravidlo obsahuje i přepis na prázdný řetězec, který původní gramatika neobsahuje.

=== Příklad 2 ===
Tato bezkontextová gramatika generuje aritmetické výrazy s proměnnými ''x'', ''y'', ''z'':

: S → x | y | z | S + S | S - S | S * S | S/S | (S)

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.

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

: S → U | V
: U → TaU | TaT
: V → TbV | TbT
: T → aTbT | bTaT | ε

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.

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

: S → bSbb | A
: A → aA | ε

=== 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:

: (1) S → S + S
: (2) S → 1
: (3) S → a

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

Rozdíl mezi levou a pravou derivací je důležitý, protože ve většině [[parsování|parsovacích]] transformací vstupu je definován kus kódu pro každé pravidlo gramatiky. Proto je důležité při [[parsování]] se rozhodnout, zdali zvolit levou nebo pravou derivaci, protože ve stejném pořadí se budou provádět části programu. Podobně jako [[LL syntaktický analyzátor]] a [[LR syntaktický analyzátor]].

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:

: S → S + S (1)
: &nbsp;&nbsp; → S + S + S (1)
: &nbsp;&nbsp; → 1 + S + S (2)
: &nbsp;&nbsp; → 1 + 1 + S (2)
: &nbsp;&nbsp; → 1 + 1 + a (3)

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

: { { { 1 }<sub>S</sub> + { 1 }<sub>S</sub> }<sub>S</sub> + { a }<sub>S</sub> }<sub>S</sub>
kde { ... }<sub>S</sub> rozpoznaný jako podřetězec S. Tato hierarchie může být také znázorněna jako strom:

            S
           /|\
          / | \
         /  |  \
        S  '+'  S
       /|\      |
      / | \     |
     S '+' S   'a'
     |     |
    '1'   '1'

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:

: S → S + S (1)
: &nbsp;&nbsp; → 1 + S (2)
: &nbsp;&nbsp; → 1 + S + S (1)
: &nbsp;&nbsp; → 1 + 1 + S (2)
: &nbsp;&nbsp; → 1 + 1 + a (3)

ta definuje následný syntaktický strom:

            S 
           /|\
          / | \
         /  |  \
        S  '+'  S
        |      /|\
        |     / | \
       '1'   S '+' S
             |     |
            '1'   'a'

Pokud pro určitý řetězec v jazyce gramatiky existuje více než jeden parsovací strom, potom se tato gramatika nazývá ''[[nejednoznačná gramatika]]''. Některé gramatiky se dají těžko rozebírat, protože syntaktický analyzátor neví, které z přepisovacích pravidel má použít. Obvykle mnohoznačnost je charakteristická pro gramatiku, což neplatí pro jazyk. Jednoznačná gramatika může také generovat stejný bezkontextový jazyk jako nejednoznačná gramatika. Nicméně existují jazyky, které nelze vygenerovat žádnou jednoznačnou gramatikou, ty pak nazýváme podstatně nejednoznačné.

== Normální formy ==
Ke každé bezkontextové gramatice lze sestrojit gramatiku v [[Chomského normální forma|Chomského normální formě]] a v [[Greibachové normální forma|Greibachové normální formě]], které jsou s původní gramatikou ekvivalentní. Ekvivalentní gramatiky jsou takové, které generují stejný jazyk.

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

== Nerozhodnutelné problémy ==
Ačkoli některé operace s bezkontextovými gramatikami jsou rozhodnutelné v jejich omezené síle, bezkontextové gramatiky se zajímají i o nerozhodnutelné problémy. Jeden z nejjednodušších a nejvíce řešených problémů je zda gramatika přijme všechny řetězce (slova) daného jazyka. Na řešení tohoto problému může být použit dobře známý [[Turingův stroj]]. Redukce využívá koncept ''[[historii výpočtu|historie výpočtu]]'', kde pomocí řetězce popisujeme celkový výpočet [[Turingův stroj|Turingova stroje]]. Dokážeme vytvořit bezkontextovou gramatiku, která generuje všechna slova, která neakceptují historii výpočtu pro specifický Turingův stroj pro jeho specifický vstup, čili přijímá všechna slova pouze pokud tento stroj nepřijímá tento vstup.

== Odkazy ==

=== Reference ===
<references />

=== Externí odkazy ===
* [http://www1.osu.cz/home/habibal/publ/rabj2.pdf Regulární a bezkontextové jazyky II.] {{Wayback|url=http://www1.osu.cz/home/habibal/publ/rabj2.pdf |date=20200531060430 }}

{{Formální jazyky a gramatiky}}
{{Autoritní data}}

[[Kategorie:Formální jazyky]]