Bezkontextové jazyky a jejich modely
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
Pushdown automaton
Jsou to vlastně konečné automaty rozšířené o zásobník. Používají se při syntaktické analýze 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 (Z0 ∈ 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á:1)
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 zdola nahoru.
Bezkontextové gramatiky
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