Rozšířené zásobníkové automaty
Rozšíření zásobníkového automatu, které budeme probírat v tomto dokumentu, je míněno tak,
že se změní způsob čtení symbolů ze zásobníku. Zatímco u obyčejného PDA jsme mohli (destruktivně)
číst pouze 1 symbol, u rozšířeného PDA máme možnost „vidět na libovolné množství
symbolů, speciálně nemusíme se na zásobník podívat vůbec. Zavedení takového typu automatu
nám pomůže při tzv. Nedeterministické syntaktické analýze zdola nahoru, kterou budeme
probírat v další kapitole.
Definice – rozšířený zásobníkový automat
Rozšířený zásobníkový automat je sedmice R = (Q, Σ, Γ, δ, q0, Z0, F), kde všechny symboly mají
tentýž význam jako u obyčejného PDA s výjimkou přechodové funkce δ, která je zobrazením
• z konečné podmnožiny množiny Q × (Σ ∪ {ε}) × Γ∗
• do konečných podmnožin množiny Q × Γ∗
.
Poznámka.
V definici rozšířeného PDA je velmi důležité uvést, že se jedná o konečné zobrazení. Proto je
definiční obor i obor hodnot zaveden jako konečná podmnožina množiny. Pokud bychom to
explicitně neuvedli, jednalo by se o zobrazení mezi dvěma nekonečnými množinami. To je však
v rozporu s naším cílem: konečně reprezentovat nekonečné jazyky.
Poznámka.
Pojmy konfigurace, akceptování koncovým stavem či prázdným zásobníkem zůstávají stejné,
pouze krok výpočtu se malinko změní v tom smyslu, že
(p, aw, γ1α) → (q, w, γ2α), právě když δ(p, a, γ1) obsahuje dvojici (q, γ2),
kde γ1, γ2, α ∈ Γ∗
jsou libovolné řetězce zásobníkových symbolů, p, q ∈ Q, a ∈ Σ, w ∈ Σ∗
.
V obyčejném PDA jsme místo řetězce γ1 ∈ Γ∗
měli pouze A ∈ Γ, tedy jeden symbol.
Příklad 1.
Mějme rozšířený zásobníkový automat R = ({q0, p, f}, {a, b, c, d}, {A, B, Z}, δ, q0, Z, {f}), kde δ
je definována takto:
1. δ(q0, a, ε) = {(q0, A)}
2. δ(q0, b, ε) = {(q0, B)}
3. δ(q0, ε, ε) = {(p, ε)}
4. δ(p, a, A) = {(p, ε)}
5. δ(p, b, B) = {(p, ε)}
6. δ(p, c, AA) = {(p, ε)}
7. δ(p, c, BBB) = {(p, ε)}
8. δ(p, d, Z) = {(f, ε)}
Všimněte si přechodů 1, 2, 3, kde nečteme ze zásobníku nic a pouze do něj zapisujeme (symbol
1
A nebo B), naopak u přechodů 6, 7 čteme více než jeden symbol. Naznačíme si výpočet na slově
aabbbccd:
(q0, aabbbccd, Z) →1 (q0, abbbccd, AZ)
→1 (q0, bbbccd, AAZ)
→2 (q0, bbccd, BAAZ)
→2 (q0, bccd, BBAAZ)
→2 (q0, ccd, BBBAAZ)
→3 (p, ccd, BBBAAZ)
→7 (p, cd, AAZ)
→6 (p, d, Z)
→8 (f, ε, ε)
Poznámka.
Tradičně nás bude zajímat, zda se rozšířením obyčejného PDA mění i jeho popisovací síla, tj.
zda platí, že pokud dokážeme sestrojit rozšířený PDA přijímající libovolný jazyk L, umíme
vytvořit i obyčejný PDA akceptující L? Následující věta potvrzuje, že je tomu tak.
Věta.
Ke každému rozšířenému PDA R existuje obyčejný PDA M takový, že L(M) = L(R).
Idea důkazu.
Je patrné, že jediný problém, který je nutné řešit, je potenciál automatu R číst více než jeden
symbol z vrcholu zásobníku. V důkazu si pomůžeme tím, že obyčejný PDA M zkonstruujeme
s rozdílně pojatou množinou stavů.
Buď tedy R = (Q, Σ, Γ, δ, q0, Z0, F) rozšířený PDA přijímající bez újmy na obecnosti koncovým
stavem. Stavy nového automatu M budeme zapisovat jako uspořádané dvojice (p, α),
kde p ∈ Q a α ∈ Γ∗
je řetězec zásobníkových symbolů, které jsou aktuálně na vrcholu zásobníku
původního automatu R. 2. složku stavu (p, α) si představte jako jakousi cache paměť, jejíž
stav budeme v závislosti na výpočtu měnit. Její délku stanovíme podle toho, jaký je maximální
počet symbolů, které je potřeba v jednom kroku přečíst ze zásobníku. Např. v příkladu 1 by
délka cache paměti byla pouze tři, protože nejdelší možný řetězec čtený ze zásobníku byl BBB
v případě přechodu 7.
V důkazu si formálně vysvětlíme, jak udržovat cache paměť a zásobník aktuální po celou
dobu výpočtu a zajistit, aby jejich zřetězením byl řetězec, který byl u původního rozšířeného
PDA na zásobníku.
Důkaz.
Nechť R = (Q, Σ, Γ, δ, q0, Z0, F) je rozšířený zásobníkový automat. Položme
m = max{|α|; δ(q, a, α) = ∅},
tj. m je maximální počet zásobníkového řetězce, pro který je δ definována. Zkonstruujeme nový
zásobníkový automat P = (Q1, Σ, Γ1, δ1, q1, Z1, F1), kde
2
• Q1 = {[q, α] | q ∈ Q, α ∈ Γ∗
1, 0 ≤ |α| ≤ m} – stavy jsou nově definovány jako dvojice, kde 1.
složka je původní stav automatu R a 2. složka představuje obsah cache paměti. Všimněte
si, že nestanovujeme délku řetězce α přímo na m. V dalším si ukážeme, že může nastat
situace, kdy cache paměť nemá přesně m symbolů a že ji musíme dodatečně aktualizovat
a doplnit symboly na zásobníku.
• Γ1 = Γ ∪ {Z1}, kde Z1 je nově přidaný symbol.
• q1 = [q0, Z0Zm−1
1 ] – na začátku výpočtu vložíme do cache paměti původní počáteční
symbol zásobníku Z0 a za něj dáme „výplně , tj. několik symbolů Z1 tak, abychom měli
měli cache paměť plnou (proto je vloženo právě m − 1 symbolů Z1).
• F1 = [q, α], kde q ∈ F je původní koncový stav automatu R a α ∈ Γ∗
1 libovolný řetězec.
Nyní nám chybí pouze vysvětlení toho, jak bude pracovat přechodová funkce δ1. Zobecněme si,
jak může přechod v rozšířeném zásobníkovém automatu R vypadat:
δ(q, a, X1X2 . . . Xk) obsahuje dvojici (r, Y1Y2 . . . Yl),
kde q, r ∈ Q jsou stavy, a ∈ Σ vstupní symbol, X1, . . . , Xk, Y1, . . . , Yl ∈ Γ1 zásobníkové symboly.
Je zřejmé, že k ≤ m, tj. délka řetězce X1X2 . . . Xk je maximálně m. Nový automat P má tento
řetězec uložený v cache paměti, navíc tam může mít ještě nějaký řetězec α.
Mohou nastat dvě různé situace: buď l ≥ k nebo l < k, tj. buď je nově zapisovaný řetězec
Y1Y2 . . . Yl delší než X1X2 . . . Xk nebo kratší. Obě možnosti si rozebereme:
1. případ: l ≥ k: přechodovou funkci δ1 v tom případě definujeme takto:
δ1([q, X1X2 . . . Xkα], a, Z) obsahuje ([r, β], γZ),
kde platí, že Z ∈ Γ1 je libovolný zásobníkový symbol a βγ = Y1Y2 . . . Ylα, což si raději znázorníme
na následujícím obrázku:
a
d( )q, a, X X ...X1 2 k Z
zásobník
X1
cache
X2 ........ Xk
a
Z
Z
Z
Z
a
(r, Y Y ...Y1 2 l)
az
zásobník
Y1
cache
Y2 ........ Yl
ac
Z
Z
l >= k
Na obrázku jste si asi všimli, že cache paměť obsahuje ve výsledku kromě řetězce Y1Y2 . . . Yl
ještě řetězec αC, zásobník navíc αZ . Platí, že αc.αz = α, kde α byl původní řetězec, který v
cache paměti následoval za X1X2 . . . Xk. Jelikož však l ≥ k, „vytlačil řetězec Y1Y2 . . . Yl některé
symboly α na zásobník. Snad je patrné, že řetězec αc je to, co ještě zůstalo v cache paměti,
zbytek (αz) byl přesunut na zásobník. Navíc |Y1Y2 . . . Ylαc| = m.
3
Je samozřejmě možné, že délka řetězce Y1Y2 . . . Yl je větší než kapacita cache paměti, tj.
|Y1Y2 . . . Yl| ≥ m. V tom případě je celý řetězec α přesunut na zásobník (αc = ε), přičemž nad
ním můžou být i některé symboly řetězce Y1Y2 . . . Yl. Každopádně musí platit, že zřetězíme-li
obsah cache paměti a zásobníku, dostaneme Y1Y2 . . . YlαZ.
2. případ: l < k: přechodovou funkci δ1 v tom případě definujeme takto:
δ1([q, X1X2 . . . Xkα], a, Z) obsahuje ([r, Y1Y2 . . . YlαZ], ε),
kde opět platí, že Z ∈ Γ1 je libovolný zásobníkový symbol. Krok výpočtu ve 2. případě si opět
znázorníme na obrázku:
a
d( )q, a, X X ...X1 2 k Z
zásobník
X1
cache
X2 ........ Xk
a
Z
Z
Z
Z
a
(r, Y Y ...Y1 2 l)
zásobník
Y1
cache
Y2 ........ Yl
l < k
a
Z
Z
Z
Z?Z
Vzhledem k tomu, že jsme do cache paměti umístili méně symbolů, než kolik tam původně bylo,
může se stát, že nebude zcela zaplněná. Je to naznačeno i na předchozím obrázku, kde po výpočetním
kroku je v cache paměti řetězec Y1Y2 . . . Yl, dále je zde i Z, který jsme z vrcholu
zásobníku přesunuli. Řešením je zařazení následujících přechodů:
δ1([q, α], ε, Z) = ([q, αZ], ε),
kde q ∈ Q, Z ∈ Γ1 jsou libovolné a pro α ∈ Γ∗
1 platí, že |α| < m. Bez čtení vstupu dostáváme ze
zásobníku do cache paměti potřebné množství symbolů.
Korektnost: k ověření korektnosti je potřeba ukázat, že platí:
(q, aw, X1X2 . . . XkXk+1 . . . Xn) →R (r, w, Y1Y2 . . . YlXk+1 . . . Xn) ⇐⇒ ([q, α], aw, β) →P ([r, α ], β ),
kde:
1. αβ = X1X2 . . . XnZm−n
1 ,
2. α β = Y1Y2 . . . YlXk+1 . . . XnZm−n
1 ,
3. |α| = |α | = m,
4. mezi těmito dvěma konfiguracemi automatu P neexistuje žádná jiná konfigurace taková,
že by 2. složka stavu (tj. cache paměť) měla délku rovnou konstantě m.
Poznámka.
Je potřeba uvést, že uvedený důkaz je těžko aplikovatelný do praxe, neboť s rostoucí délkou
cache paměti roste velmi výrazně i počet přechodů.
4