21 - Bezkontextové jazyky a jejich modely

1. Bezkontextové gramatiky
2. Zásobníkové automaty

Nechť G = (N, T, P, S) je BKG. … Máme nějakou bezkontextovou gramatiku
Nechť u, v ∈ (N ∪ T)* … Dále máme 2 řetězce u a v, které se skládají z terminálů a neterminálů naší gramatiky
a p = A → x ∈ P. a ještě máme jedno pravidlo p, které říká, že neterminál A se dá přepsat terminálem x

Potom, uAv přímo derivuje uxv za použití p v G, zapsáno uAv ⇒ uxv [p] nebo zjednodušeně uAv ⇒ uxv.
Jednoduše řečeno - posloupnost uAv můžeme přepsat na uxv díky pravidlu p

Pokud bude derivačních kroků více za sebou, budeme jim říkat Sekvence derivačních kroků a značit ⇒ⁿ, kde n nám bude říkat, v kolika derivačních krocích přeměníme jednu posloupnost terminálů/neterminálů na druhou

Nechť G = (N, T, P, S) je BKG. Jazyk generovaný BKG G, L(G), je definován: L(G) = {w: w ∈ T*, S ⇒* w}
Máme nějakou posloupnost terminálů w. Pokud dokážeme v nějaké sekvenci derivačních kroků přepsat startovací neterminál naší BKG do této posloupnosti terminálů, je tento jazyk generovaný naší BKG.

Bezkontextový jazyk je jazyk, pro který existuje bezkontextová gramatika, která tento jazyk generuje.

• grafické znázornění jednotlivých pravidel
• použití jednotlivých pravidel znázorníme derivačním stromem (skládá se z pravidlových stromů)
• k sestavení derivačního stromu nás může dovést více řešení - my se budeme zajímat o následující dvě:
  1. Nejlevější derivace ⇒_lm - přepisujeme vždy nejlevější neterminál
  2. Nejpravější derivace ⇒_rm - přepisjeme vždy nejpravější neterminál
  • všimněte si, že jsme došli ke stejnému řešení

Nejlevější derivace	Nejpravější derivace

Nechť G = (N, T, P, S) je BKG. Pokud existuje řetězec x ∈ L(G) s více jak jedním derivačním stromem, potom G je nejednoznačná. Jinak G je jednoznačná.

• je to Konečný automat rozšířený o zásobník

Grafický popis	Výpočet

• jeden výpočetní krok ZA
• značíme |- … např. xApay |– xwqy [r]
• více přechodů za sebou - sekvence přechodů

Nechť M = (Q, Σ, Γ, R, s, S, F) je ZA.
1.) Jazyk přijímaný ZA M přechodem do koncového stavu, značen jako L(M)_f, je definován:
L(M)_f = {w: w ∈ Σ*, Ssw |–* zf, z ∈ Γ*, f ∈ F}
2.) Jazyk přijímaný ZA M vyprázdněním zásobníku, značen jako L(M)_ε, je definován:
L(M)_ε = {w: w ∈ Σ*, Ssw |–* zf, z = ε, f ∈ Q}
3.) Jazyk přijímaný ZA M přechodem do koncového stavu a vyprázdněním zásobníku, značen jako L(M)_fε, je definován:
L(M)_fε = {w: w ∈ Σ*, Ssw |–* zf, z = ε, f ∈ F}

• z každé konfigurace lze provést pouze 1 přechod
• ZA jsou silnější než DZA (DZA přijímá podmnožinu jazyků přijímaných ZA)

• zásobníkový automat, který se od obyčejného ZA liší v definici přechodu R
  • konečná množina pravidel tvaru: vpa → wq, kde v, w ∈ Γ* , p, q ∈ Q, a ∈ Σ ∪ {ε}
  • ze zásobníku můžeme přečíst celý řetězec a ne pouze znak

• existují dva základní přístupy:
  1. SA shora dolů - z S směrem ke vstupnímu řetězci
     • porovnávací pravidlo - pro každé a ∈ Σ: přidej asa → s do R
     • expanzivní pravidlo - pro každé A → a₁…a_n ∈ P v G, přidej As → a_n…a₁s do R
  2. SA zdola nahoru - ze vstupního řetězce směrem k S
     • shiftovací pravidlo - pro každé a ∈ Σ: přidej sa → as do R
     • redukční pravidlo - pro každé A → x ∈ P v G: přidej xs → As do R
     • finishovací pravidlo - #Ss → f

Shora dolů	Zdola nahoru