====== Bezkontextové jazyky a jejich modely ======
[[wp>Context-free language]]

Bezkontextové gramatiky a zásobníkové automaty mají stejnou vyjadřovací sílu. Jsou to modely bezkontextových jazyků.
===== Zásobníkové automaty =====
[[wp>Pushdown automaton]]

Jsou to vlastně konečné automaty rozšířené o zásobník. Používají se při syntaktické analýze **[[prekladac#shora dolu|shora dolů]]**.

Sedmice:
  * Množina stavů (Q)
  * Vstupní abeceda (T)
  * Zásobníková abeceda (Z)
  * Parciální přechodová funkce (δ)
  * Počáteční stav (q ∈ Q)
  * Počáteční symbol zásobníku (Z<sub>0</sub> ∈ Z)
  * Množina koncových stavů (F)

**Parciální přechodová funkce** -- Vezmu aktuální stav, načtu symbol, vezmu vrchol zásobníku a podle toho určím do jakého stavu se přesunu a co na zásobník vrátím.

Jsou dvě možnosti jak zásobníkový automat přijímá:((Vždy ale musí dočíst slovo. Algoritmicky lze automat mezi oběma možnostmi převádět.))
  * Koncovým stavem
  * Prázdným zásobníkem

==== Rozšířený zásobníkový automat ====
Celý rozdíl spočívá v tom, že ze zásobníku můžu odebírat i přidávat více než jeden symbol. Používá se u syntaktické analýzy **[[prekladac#zdola nahoru|zdola nahoru]]**. 

===== Bezkontextové gramatiky =====
[[wp>Context-free grammar]]

Bezkontextová gramatika je čtveřice G=(N,T,P,S), kde
  * N je abeceda **neterminálů**
  * T je abeceda **terminálů**, přičemž N ∩ T = ∅ (tj. prvky obou množin jsou různé)
  * P je konečná množina **pravidel** tvaru A → x, kde A ∈ N, x ∈ (N ∪ T)*
  * S ∈ N je **počáteční neterminál**

  * **Derivační strom** -- jiný zápis pro odvození slova.
  * ** Nejednoznačná gramatika** -- pokud se slovo gramatiky dá odvodit více různými derivačními stromy (levé i pravé derivace jsou ekvivalentní), je gramatika nejednoznačná.
  * **Jednoznačnost jazyka** -- pokud existuje alespoň jedna jednoznačná gramatika, která definuje jazyk, pak je jazyk jednoznačný. Nejednoznačnost nelze dokázat!

==== Redukce bezkontextových gramatik ====
=== Vlastní gramatika ===
  - Bez nepoužitelných symbolů
  - Bez ε-pravidel
  - Necyklická

Z vlastní gramatiky se dál tvoří Chomského normální forma a Greibachové normální forma.

===== Shrnutí =====
  * bezkontextový jazyk: formální jazyk, generován bezkontextovou gramatikou, "závorkový jazyk" (lze se libovolně zanořovat)
  * zásobníkový automat: umět sedmici, používá se pro syntaktickou analýzu shora dolů, rozšířený umí číst ze zásobníku celý řetězec a používá se zdola nahoru (jak obyčený tak rozšířený zásobníkový automat mohou při přechodové funkci vložit na zásobník řetězec) 
  * bezkontextová gramatika: generuje bezkontextový jazyk, umět čtveřici
  * generovaná slova lze rozepsat jako sekvenci odvození, nebo jako derivační strom
  * nejednoznačná gramatika: existuje více derivačních stromů, pomocí kterých lze rozepsat výraz