Kalábovi

Kalábovic wikina

Uživatelské nástroje

Nástroje pro tento web


pitel:isz:bezkontextove_jazyky

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

  1. Bez nepoužitelných symbolů
  2. Bez ε-pravidel
  3. 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
1)
Vždy ale musí dočíst slovo. Algoritmicky lze automat mezi oběma možnostmi převádět.
/var/www/wiki/data/pages/pitel/isz/bezkontextove_jazyky.txt · Poslední úprava: 03. 07. 2012, 13.53:44 (upraveno mimo DokuWiki)