Kalábovi

Kalábovic wikina

Uživatelské nástroje

Nástroje pro tento web


pitel:isz:bezkontextove_jazyky

Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

Odkaz na výstup diff

pitel:isz:bezkontextove_jazyky [03. 07. 2012, 13.53:44] (aktuální)
Řádek 1: Řádek 1:
 +====== 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
/var/www/wiki/data/pages/pitel/isz/bezkontextove_jazyky.txt · Poslední úprava: 03. 07. 2012, 13.53:44 (upraveno mimo DokuWiki)