Bezkontextové gramatiky a jazyky

Bezkontextová gramatika je formální gramatika, ve které mají všechna přepisovací pravidla tvar
A → β
A je neterminál/proměnná a β je řetězec složený z terminálů nebo neterminálů/proměnných.

Gramatika je určena

Konečnou množinou neterminálních symbolů
Konečnou množinou terminálních symbolů, která nemá společné prvky s množinou neterminálů (Někdy také nazýváme tuto množinu abecedou jazyka, jež je generovaný touto gramatikou)
Počátečním neterminálem S
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ů

Bezkontextová gramatika je speciálním případem kontextové gramatiky, akorát kontext je prázdný.

Množina všech řetězců, jež jsou tuto gramatikou vygenerované se nazývá bezkontextový jazyk.

Co je to kontext ?

Kontextem se myslí symboly, které se nacházejí vedle neterminálů. U bezkontextové gramatiky platí, že nezávisle na tom, které symboly obklopují neterminál z levé strany, tak je možné tento neterminál nahradit některým přepisovacím pravidlem.

A → xBy
B → a | A

A => xAy => xxByy

Termíny/Pojmy

Přepsání : 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. Značí se =>.
Odvození : postup, při kterém se na řetězec uplatní konečný počet (žádné, jedno nebo více) přepsání.
Větná forma : 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í.
Řetězec generovaný gramatikou : méně formálně věta gramatiky je větná forma, která je tvořena pouze terminálními symboly.
Jazyk generovaný gramatikou : množina všech řetězců, generovaných gramatikou.
Levá derivace neboli levé odvození : 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í.
Pravá derivace neboli pravé odvození : 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).

Vlastnosti bezkontextových jazyků

Jak už jsme řekli, bezkontextový jazyk je generovaný bezkontextovou gramatikou. Na základě Chomského hierarchie se tedy jedná o jazyk generovaný gramatikou typu 2.

Jazyk je přijímaný zásobníkovým automatem (nikoliv konečným automatem, ten je schopen přijímat pouze jazyky generované regulérní gramatikou).
Jazyk je uzavřený vůči zřetězení, sjednocení, iteraci, substituci a morfismu s regulárním jazykem. To znamená, že výsledkem těchto operací stále bude bezkontextový jazyk
Jazyk není uzavřená vůči průniku a rozdílu s regulárním jazykem. Výsledkem těchto operací již nebude bezkontextový jazyk.
Každý regulární jazyk je také bezkontextový, ale obráceně to neplatí.
Když se během posloupnosti přepisů někde objeví terminální symbol, už tam zůstane.
Přepisy různých proměnných jsou navzájem nezávislé:
Mámeli řetěz xAyBz, můžeme postupně přepisovat proměnné A a B v libovolném pořadí.

Příklady zápisu

Gramatika je zadána nějakým přepisovacím pravidlem. V našem případě jsme dostaly následující přepisovací pravidlo :

S → aSb | ab

Vidíme, že toto přepisovací pravidlo odpovídá tvaru přepisovacího pravidla pro bezkontextovou gramatikou:

A → β (A je neterminál a β je řetězec složený z terminálů/neterminálů)

Pokud bychom chtěli získat řetězec, jež je generovaný touto gramatikou, použijeme k tomu odvození.

Rozepíšeme se naše pravidlo a postupně nahrazujeme neterminály, dokud nedostaneme požadovaný řetězec, nebo dokud nám nedojdou neterminální symboly na pravé straně.

S → aSb
S → ab
→ aaSbb
→ aaaSbbb
→ aaaabbbb

Příklady řetězců generovaných touto bezkontextovou gramatikou: ab, aabb, aaabbb, ...

Zápis může být také proveden tzv. derivačním stromem.

Zápis pomocí derivačního stromu

Mějme bezkontextovou gramatikou danou přepisovacími pravidly ve tvaru:

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

Použijme nyní postup levého odvození pro získání řetězce 1 + 1 + a.

S → S + S (1)
=> S + S + S (1)
=>1 + S + S (2)
=> 1 + 1 + S (2)
=> 1 + 1 + a (3)

Všimněme si, jak levé odvození funguje. Nahrazuje vždy první neterminální symbol na pravé straně. Pravé odvození by nahrazovalo vždy poslední neterminální symbol na pravé straně.

Tento postup může být znázorněn také jako strom:

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

Tomuto se říká konkrétní syntaktický strom řetězce

K výsledku (1 + 1 + a) můžeme dojít i jiným způsobem

S → S + S (1)
=> 1 + S (2)
=> 1 + S + S (1)
=> 1 + 1 + S (2)
=> 1 + 1 + a (3)

       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 (parser) neví, které z přepisovacích pravidel má použít. Obvykle mnohoznačnost je charakteristická pro gramatiku, což neplatí pro jazyk.

Normální formy

Používají se ke zjednodušení bezkontextových gramatik. Ke každé bezkontextové gramatice lze sestrojit gramatiku v Chomského normální formě a v Greibachové normální formě, které jsou s původní gramatikou ekvivalentní. Ekvivalentní gramatiky jsou takové, které generují stejný jazyk.

Chomského normální forma:
- všechna odvozovací pravidla tvaru:
- A → BC nebo
- A → a nebo
- S → ε (je povoleno pokud gramatika generuje prázdný řetězec a zároveň se S nevyskytuje na pravé straně žádného pravidla)
- kde A, B a C jsou neterminály, 'a' je terminál, S je startovní neterminál a ε je prázdný řetězec, přičemž B ani C nemohou být startovacím neterminálem.
- Každá gramatika v Chomského normální formě je bezkontextová a naopak, každou bezkontextovou gramatiku lze transformovat do Chomského normální formy.
- S výjimkou volitelného pravidla S → ɛ jsou všechna pravidla nezkracující, tzn. při každém odvození je každý řetězec stejně dlouhý nebo delší než předchozí (ve významu času) řetězec. Jelikož všechna pravidla odvozující neterminály transformují jeden neterminál na právě dva, je parsovacím stromem binární strom a jeho výška je maximálně délka generovaného řetězce.
Greibachové normální forma:
- všechna odvozující pravidla mají tvar:
- A → aX nebo
- S → ε
- Přičemž A je neterminál, 'a' je terminál, S je startovní neterminál, X je (případně prázdná) posloupnost neterminálních symbolů (ve které se nevyskytuje S, pokud gramatika obsahuje pravidlo S → ε) a ɛ je prázdný řetězec.
- Gramatika v Greibachové normální formě postrádá levou rekurzi. Každá bezkontextová gramatika může být transformována do Greibachové normální formy. Gramatika v Greibachové normální formě je díky absenci levé rekurze ideální k sestrojení predikativního parseru za pomocí LL gramatiky.

Proč ale chceme upravovat přepisovací pravidla, aby vyhovovali jedné ze dvou norem? Důvodem je sestrojení něčeho, co dokáže v konečném čase říci, zdali daný řetěz patří do jazyka, či nikoliv.

Motivace: Chceme vědět, jestli řetězec patří do jazyka, jež je popsaný určitými přepisovacími pravidly.

Zásobníkový automat


obr. 1: Zásobníkový automat (PDA) Dostupné z: https://elearning.jcu.cz/pluginfile.php/279723/mod_resource/content/9/prezentace.pdf

Nedeterministický zásobníkový automat je uspořádaná sedmice
M = (Q, Σ, Γ, δ, q0, z, F)

Q je konečná množina stavů řídící jednotky;
Σ je konečná vstupní abeceda;
Γ je konečná množina symbolů – abeceda zásobníku;
δ je přechodová funkce – funkce z Q × (Σ ∪ {λ}) × Γ do množiny všech konečných podmnožin kartézského součinu Q × Γ
- Příklad: δ(q0, a, 1) = {(q1, 11)} toto čteme jako : Jsme ve stavu q0, pokud je na vstupu 'symbol a' a v zásobníku 'symbol 1', jdi do stavu q1 a do zásobníku přidej symboly '11'.
q0 ∈ Q je počáteční stav řídící jednotky;
z ∈ Γ je počáteční symbol zásobníku ;
F ⊆ Q je množina koncových stavů řídící jednotky.

Automat lze vyjádřit:

Přechodovou tabulkou
grafem přechodů
Obojí získáme z přepisovacích pravidel bezkontextové gramatiky, které jsou pokud možno v jedné ze dvou normálních forem

Rozlišujeme dva druhy zásobníkových automatů

deterministické (DPA)
- Je pouze jedna možnost jak přejít ze stavu do stavu pomocí jednoho symbolu
- Každý DPA lze převést na NDPA
- Jazyk přijímaný DPA je podmnožinou jazyka přijímaného NDPA
- Přijímá pouze deterministické bezkontextové jazyky
nedeterministické (NDPA)
- Je více možností jak přejít ze stavu do stavu pomocí jednoho symbolu
- Ne každý NDPA lze převést na DPA
- Přijímá jak deterministické bezkontextové jazyky, tak nedeterministické

Zásobníkové automaty mohou používat lambda přechody a být stále deterministické, protože se řídí nejen symbolem na vstupu, ale i symbolem/y nacházejícím se na zásobníku. Oproti konečným automatům, které ví jen to co je (stav) a to co bude (symbol -> další stav), tak zásobníkové automaty ví i to co bylo (symboly v zásobníku). Mohou tedy rekurzivně určit následující stav na základě aktuálního stavu, vstupního znaku a předchozí sekvence znaků, jež se nachází v zásobníku. Mají paměť. Jedná se o nejjednodušší případ syntaktického analyzátoru metodou shora dolů.

Pro jednodušší konstrukci zásobníkového automatu potřebujeme, aby byla gramatika pokud možno v Greibachové normální formě (GNF).

Na základě přepisovacích pravidel lze sestrojit zásobníkový automat následovně:

vložíme S do zásobníku
simulujeme přepisovací pravidla aplikovaná vždy na nejlevější proměnnou v odvozovaném slově (= levé odvození).
- příklad :
  Mámeli na vrcholu zásobníku proměnnou A a na vstupu znak a, vybereme nějaké pravidlo tvaru
  A → ax a proměnnou A v zásobníku nahradíme řetězem proměnných x.


obr. 2: Získání přechodové tabulky z přepisovacích pravidel Dostupné z: https://elearning.jcu.cz/pluginfile.php/279723/mod_resource/content/9/prezentace.pdf

Určení, zdali je jazyk generovaný gramatikou bezkontextový

Pokud máme nějaký jazyk L, může nás zajímat, o jaký druh jazyka jde. Je jazyk bezkontextový? K tomuto účelu slouží pumpovací lemma.

Pumpovací lemma

Pumpovací lemma si zakládá na tvrzení, že pro jakýkoliv bezkontextový jazyk L je možné najít v dostatečně dlouhém řetězci generovaném jazykem dva podřetězce, které je možné n krát opakovat tak, aby výsledný řetězec stále patřil do tohoto jazyka.

Pumpovací lemma nám není schopné říct, zdali jazyk generovaný gramatikou je bezkontextový. Může nám pouze říct, že není.

Podobný princip funguje i pro regulární jazyky.

Zdroje

Wikipedie: Otevřená encyklopedie - Bezkontextová gramatika [online]. @2023 [cit. 2023-04-23]. Dostupné z: https://cs.wikipedia.org/wiki/Bezkontextov%C3%A1_gramatika
Wikipedie: Otevřená encyklopedie - Terminální a neterminální symbol [online]. @2023 [cit. 2023-04-23]. Dostupné z: https://cs.wikipedia.org/wiki/Termin%C3%A1ln%C3%AD_a_netermin%C3%A1ln%C3%AD_symbol
Wikipedia: Open encyclopedia - Pumping lemma for context-free languages [online]. @2023 [cit. 2023-04-23]. Dostupné z: https://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages
Wikipedie: Otevřená encyklopedie - Bezkontextový jazyk [online]. @2023 [cit. 2023-04-23]. Dostupné z: https://cs.wikipedia.org/wiki/Bezkontextov%C3%BD_jazyk
GeeksForGeeks - Various Properties of context free languages [online]. @2023 [cit. 2023-04-23]. Dostupné z: https://www.geeksforgeeks.org/various-properties-of-context-free-languages-cfl/
Lhotka Ladislav - Teoretická informatika [online]. @2021 [cit. 2023-04-23]. Dostupné z: https://elearning.jcu.cz/pluginfile.php/279723/mod_resource/content/9/prezentace.pdf

Státní závěrečné zkoušky - Aplikovaná informatika