21 - Zásobníkové automaty (jazyky přijímané ZA, varianty ZA)

Question 1

Zásobníkový automat

Answer 1

7-ice M = (Q, Σ, Γ, δ, q₀, Z₀, F)
• Q – konečná množina stavů
• Σ – konečná vstupní abeceda (Sigma)
• Γ – konečná zásobníková abeceda (Gamma)
• δ – přechodová funkce ve tvaru δ: Q×(Σ∪{ε})×Γ→2^(Q×Γ^∗ ) (Delta)
○ Je to konečná množina kartézského součinu.
• q₀∈Q – počáteční stav
• Z₀∈Γ – počáteční symbol zásobníku
• F⊆Q – množina koncových stavů

Question 2

Konfigurace ZA (počáteční, koncová), přechodová funkce a jazyk přijímaný ZA

Answer 2

Konfigurace ZA = trojice (q,w, α)∈Q×Σ^×Γ^ tj. stav, zbývající vstup a obsah zásobníku
Počáteční konfigurace = trojice (q0,w,Z_0) tj. počáteční stav,celý vstup a startovací symbol zásobníku
Koncová konfigurace = trojice (q ∈ F, ε, α) tj. některý koncový stav a prázdný vstup a libovolný obsah zásobníku

Přechod ⊢ ZA je definován jako (q,aw,Zγ) ⊢ (q′,w,βγ) ⇔ (q′,β) ∈ δ(q,a,Z), Pokud a = ε, pak se jedná o ε-přechod.

Jazyk přijímaný ZA je L(M)={w|(q0,w,Z0)⊢∗(qf,ε,γ)∧qf ∈F}.
• tj. množina všech řetězců pro které ZA přejde z počáteční do koncové konfigurace
• Bezkontextové jazyky (Jazyky přijímané ZA jsou jazyky třídy 2 Chomského hierarchie (bezkontextové jazyky))

Question 3

Typy přijetí jazyka v ZA

Answer 3

Vyprázdněním zásobníku, přejitím do koncového stavu, obojím - Všechny 3 způsoby jsou ekvivalentní

ZA přijímající vyprázdněním zásobníku
Automat přijímá řetězec přechodem do koncové konfigurace (q∈Q, ϵ, ϵ)
(obvykle se zavádí speciální symbol # označující dno zásobníku aby automat mohl provádět přechody i v případě, že nepotřebuje během výpočtu mít na zásobníku žádný znak)

DZA příjimající vyprázdněním zásobníku mají striktně menší vyjadřovací sílu než DZA (nemůže přijmout např {a, aa} - prázdný zásobník po a)

Question 4

Syntaktická analýza

Answer 4

Shora dolů - Top-down - používáme zásobník pro simulaci pravidel (přidání na zásobník podle pravidel + pravidlo nahrávající vstup na zásobník)

expanzivní pavidla? (převod BKG na konečný automat?)

Přijímá prázdným zásobníkem!
Pro gramatiku (N,Σ,P,S) zkonstrujeme ZA:
P = ({q}, Σ, N ∪ Σ, δ, q, S, ∅)
• Je-li A → α pravidlo z P, pak δ(q, ε, A) ∋ (obsahuje) (q, α)
• δ(q, a, a) = {(q, ε)} pro všechna a ∈ Σ
Vytváříme levou derivaci vstupního řetezce

Zdola nahoru - bottom-up (rveme věci na zásobník, pokud máme pravou stranu pravidla na zásobníku, redukujeme, chceme se dostat ke startovnímu NONterminálu :) )

Vyžaduje rozšířený zásobníkový automat!
Pro gramatiku (N,Σ,P,S) zkonstrujeme rozšířený ZA:
P = ({q, r}, Σ, N ∪ Σ ∪ {#}, δ, q, #, {r})
	• Redukce: Je-li A → α pravidlo z P, pak δ(q, ε, α) ∋ (obsahuje) (q, A)    (tj. redukujeme vrchol zásobníku dle přepisovacích pravidel)
	• Shift: δ(q, a, ε) = {(q, a)} pro všechna a ∈ Σ   (tj. skládáme znaky na zásobník)
	• Accept: δ(q, ε, S#) = {(r, ε).    (tj. po zredukování všeho na startovací nonterminál jdeme do koncového stavu)
Syntaktický analyzátor vytvářející pravou derivaci vstupu postupnými redukcemi l-fráze.

V podstatě automat postupně přesouvá prefix vstupu na zásobník, pokud je na vrcholu zásobníku řetezec odpovídající pravé straně nějakého pravidla redukujeme jej na levou stranu tohoto pravidla, kterou umístíme na zásobník, musíme skončit se startovacím nonterminálem gramatiky na zásobníku.

Question 5

Varianty (ZA) - Rozšířený ZA

Answer 5

• δ - funkce přechodu (zobrazení Q×(Σ∪{ϵ})×Γ^* → 2^((Q×Γ^*))) == Může číst ze zásobníku celé řetězce nejen symboly.
Může provádět přechody i s prázdným zásobníkem (nemusí číst symbol ze zásobníku)
Je ekvivalentní se ZA.

Question 6

Varianty (ZA) - Deterministický ZA

Answer 6

je ZA, pro který platí, že ∀a ∈ Σ : |δ(q, a, z)| ≤ 1 ∧ δ(q, ε, z) = ∅ nebo ∀a∈Σ: δ(q,a,z)=∅∧|δ(q,ε,z)|≤1.

Přijímá deterministické bezkontextové jazyky.
Striktně menší vyjadřovací síla než nedeterministický ZA. (L = {ww^R})