Uživatelské nástroje
pitel:isz:bezkontextove_jazyky
no way to compare when less than two revisions
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
| — | pitel:isz:bezkontextove_jazyky [30. 12. 2022, 13.43:01] (aktuální) – vytvořeno - upraveno mimo DokuWiki 127.0.0.1 | ||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| + | ====== Bezkontextové jazyky a jejich modely ====== | ||
| + | [[wp> | ||
| + | Bezkontextové gramatiky a zásobníkové automaty mají stejnou vyjadřovací sílu. Jsou to modely bezkontextových jazyků. | ||
| + | ===== Zásobníkové automaty ===== | ||
| + | [[wp> | ||
| + | |||
| + | Jsou to vlastně konečné automaty rozšířené o zásobník. Používají se při syntaktické analýze **[[prekladac# | ||
| + | |||
| + | 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< | ||
| + | * 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á: | ||
| + | * 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# | ||
| + | |||
| + | ===== Bezkontextové gramatiky ===== | ||
| + | [[wp> | ||
| + | |||
| + | Bezkontextová gramatika je čtveřice G=(N, | ||
| + | * N je abeceda **neterminálů** | ||
| + | * T je abeceda **terminálů**, | ||
| + | * 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í), | ||
| + | * **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á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: 30. 12. 2022, 13.43:01 autor: 127.0.0.1
Nástroje pro stránku
Kromě míst, kde je explicitně uvedeno jinak, je obsah této wiki licencován pod následující licencí: CC Attribution-Share Alike 4.0 International
