Formální jazyky a automaty
Algoritmus Cocke-Younger-Kasami, zásobníkové automaty
Jan Křetínský
Fakulta informatiky, MU Brno
Jaro 2024
C-Y-K: Příklad
Problém: Lze v dané gramatice v CNF odvodit dané slovo w? Tj. S ⇒∗
w?
2 / 17
C-Y-K: Příklad
Problém: Lze v dané gramatice v CNF odvodit dané slovo w? Tj. S ⇒∗
w?
Řešení: Pro každé neprázdné podslovo u slova w spočítáme množinu
Tu všech neterminálů, z kterých lze odvodit u.
2 / 17
C-Y-K: Příklad
Problém: Lze v dané gramatice v CNF odvodit dané slovo w? Tj. S ⇒∗
w?
Řešení: Pro každé neprázdné podslovo u slova w spočítáme množinu
Tu všech neterminálů, z kterých lze odvodit u.
S → AB | SS | a Ti,j = {X ∈ N | X ⇒∗
wi wi+1 . . . wi+j−1}
A → AA | BC | a w = abaa
B → AB | b
C → SA | b
1
4 2
3 3
2 4
1
a b a a
2 / 17
Algoritmus Cocke-Younger-Kasami
Vstup: gramatika G = (N, Σ, P, S) v CNF, slovo w = w1 . . . wn ̸= ε
Výstup: množiny Ti,j = {X ∈ N | X ⇒∗
wi . . . wi+j−1}
1: for i ← 1 to n do
2: Ti,1 ← ∅
3: for all pravidlo tvaru (A → a) ∈ P do
4: if a = wi then Ti,1 ← Ti,1 ∪ {A}
5: for j ← 2 to n do
6: for i ← 1 to n − j + 1 do
7: Ti,j ← ∅
8: for k ← 1 to j − 1 do
9: for all pravidlo tvaru (A → BC) ∈ P do
10: if B ∈ Ti,k ∧ C ∈ Ti+k,j−k then Ti,j ← Ti,j ∪ {A}
3 / 17
Zásobníkové automaty
1Zápis PFin(Q × Γ∗) značí množinu všech konečných podmnožin množiny Q × Γ∗.
4 / 17
Zásobníkové automaty
Definice 3.36.
Nedeterministický zásobníkový automat (PushDown Automaton,
PDA) je sedmice M = (Q, Σ, Γ, δ, q0, Z0, F), kde
▶ Q je konečná množina, jejíž prvky nazýváme stavy,
▶ Σ je konečná množina, tzv. vstupní abeceda,
▶ Γ je konečná množina, tzv. zásobníková abeceda,
▶ δ : Q × (Σ ∪ {ε}) × Γ → PFin(Q × Γ∗
), tzv. (parciální) přechodová
funkce1
,
▶ q0 ∈ Q je počáteční stav,
▶ Z0 ∈ Γ je počáteční symbol v zásobníku,
▶ F ⊆ Q je množina koncových stavů.
1Zápis PFin(Q × Γ∗) značí množinu všech konečných podmnožin množiny Q × Γ∗.
4 / 17
Výpočet zásobníkového automatu
Definice 3.37.
Nechť M = (Q, Σ, Γ, δ, q0, Z0, F) je PDA.
Konfigurací nazveme libovolný prvek (p, w, α) ∈ Q × Σ∗
× Γ∗
.
Na množině všech konfigurací automatu M definujeme binární relaci
krok výpočtu | M takto:
(p, aw, Zα) | M (q, w, γα)
def
⇐⇒ ∃(q, γ) ∈ δ(p, a, Z) pro a ∈ Σ∪{ε}
Reflexivní a tranzitivní uzávěr relace | M značíme |
∗
M .
Je-li M zřejmý z kontextu, píšeme pouze | resp. |
∗
.
5 / 17
Akceptující výpočet zásobníkového automatu
Definice 3.37. (pokračování)
Jazyk akceptovaný PDA M koncovým stavem definujeme jako
L(M) = {w ∈ Σ∗
| (q0, w, Z0) |
∗
(qf , ε, α), kde qf ∈ F, α ∈ Γ∗
}
a jazyk akceptovaný PDA M prázdným zásobníkem definujeme jako
Le(M) = {w ∈ Σ∗
| (q0, w, Z0) |
∗
(q, ε, ε), kde q ∈ Q}.
6 / 17
Příklad
M = ({q0, p, f }, {a, b}, {A, B, Z}, δ, q0, Z, {f }), kde
δ(q0, a, Z) = {(q0, AZ)}
δ(q0, a, A) = {(q0, AA)}
δ(q0, a, B) = {(q0, AB)}
δ(q0, b, Z) = {(q0, BZ)}
δ(q0, b, A) = {(q0, BA)}
δ(q0, b, B) = {(q0, BB)}
δ(q0, ε, Z) = {(p, Z)}
δ(q0, ε, A) = {(p, A)}
δ(q0, ε, B) = {(p, B)}
δ(p, a, A) = {(p, ε)}
δ(p, b, B) = {(p, ε)}
δ(p, ε, Z) = {(f , Z)}
7 / 17
Příklad
M = ({q0}, {a, b}, {Z, A}, δ, q0, Z, ∅), kde
δ(q0, a, Z) = {(q0, A)}
δ(q0, a, A) = {(q0, AA)}
δ(q0, b, A) = {(q0, ε)}
8 / 17
Ekvivalence dvou způsobů akceptování
Věta 3.39.
Pro každý jazyk L platí:
L = L(N) pro nějaký PDA N ⇐⇒ L = Le(M) pro nějaký PDA M.
Důkaz. 1. koncový stav =⇒ prázdný zásobník
9 / 17
Ekvivalence dvou způsobů akceptování
Věta 3.39.
Pro každý jazyk L platí:
L = L(N) pro nějaký PDA N ⇐⇒ L = Le(M) pro nějaký PDA M.
Důkaz. 1. koncový stav =⇒ prázdný zásobník
K danému N zkonstruujeme M simulující jeho činnost.
Vejde-li N do koncového stavu, M se nedeterministicky rozhodne
▶ pokračovat v simulaci automatu N nebo
▶ přejít do nově přidaného stavu qε, v němž vyprázdní zásobník.
9 / 17
Ekvivalence dvou způsobů akceptování
Věta 3.39.
Pro každý jazyk L platí:
L = L(N) pro nějaký PDA N ⇐⇒ L = Le(M) pro nějaký PDA M.
Důkaz. 1. koncový stav =⇒ prázdný zásobník
K danému N zkonstruujeme M simulující jeho činnost.
Vejde-li N do koncového stavu, M se nedeterministicky rozhodne
▶ pokračovat v simulaci automatu N nebo
▶ přejít do nově přidaného stavu qε, v němž vyprázdní zásobník.
Komplikace:
9 / 17
Ekvivalence dvou způsobů akceptování
Věta 3.39.
Pro každý jazyk L platí:
L = L(N) pro nějaký PDA N ⇐⇒ L = Le(M) pro nějaký PDA M.
Důkaz. 1. koncový stav =⇒ prázdný zásobník
K danému N zkonstruujeme M simulující jeho činnost.
Vejde-li N do koncového stavu, M se nedeterministicky rozhodne
▶ pokračovat v simulaci automatu N nebo
▶ přejít do nově přidaného stavu qε, v němž vyprázdní zásobník.
Komplikace: N vyprázdní zásobník bez akceptování
Řešení:
9 / 17
Ekvivalence dvou způsobů akceptování
Věta 3.39.
Pro každý jazyk L platí:
L = L(N) pro nějaký PDA N ⇐⇒ L = Le(M) pro nějaký PDA M.
Důkaz. 1. koncový stav =⇒ prázdný zásobník
K danému N zkonstruujeme M simulující jeho činnost.
Vejde-li N do koncového stavu, M se nedeterministicky rozhodne
▶ pokračovat v simulaci automatu N nebo
▶ přejít do nově přidaného stavu qε, v němž vyprázdní zásobník.
Komplikace: N vyprázdní zásobník bez akceptování
Řešení: Před zahájením simulace bude u M na dně zásobníku nový
symbol, který nedovolíme odstranit jinde, než ve stavu qε.
9 / 17
Konstrukce: Nechť N = (Q, Σ, Γ, δ, q0, Z0, F).
Klademe M = (Q ∪ {q′
0, qε}, Σ, Γ ∪ {Z′
}, δ′
, q′
0, Z′
, ∅),
kde Z′
/∈ Γ, q′
0, qε /∈ Q a δ′
je definována takto:
▶ δ′
(q′
0, ε, Z′
) = {(q0, Z0Z′
)}
▶ jestliže δ(q, a, Z) obsahuje (r, γ), pak δ′
(q, a, Z) obsahuje (r, γ)
▶ δ′
(q, ε, Z) obsahuje (qε, Z)
pro všechny q ∈ F a Z ∈ Γ ∪ {Z′
}
▶ δ′
(qε, ε, Z) = {(qε, ε)}
pro všechny Z ∈ Γ ∪ {Z′
}
10 / 17
2. prázdný zásobník =⇒ koncový stav
11 / 17
2. prázdný zásobník =⇒ koncový stav
K danému M zkonstruujeme N simulující jeho činnost.
▶ N si před simulací přidá na dno zásobníku nový symbol.
▶ Je-li N schopen číst tento symbol (tj. zásobník automatu M
je prázdný) tak N přejde do nově přidaného stavu qf , který je
koncovým stavem.
11 / 17
Konstrukce: Nechť M = (Q, Σ, Γ, δ, q0, Z0, ∅).
Klademe N = (Q ∪ {q′
0, qf }, Σ, Γ ∪ {Z′
}, δ′
, q′
0, Z′
, {qf }),
kde Z′
/∈ Γ, q′
0, qf /∈ Q a δ′
je definována takto:
▶ δ′
(q′
0, ε, Z′
) = {(q0, Z0Z′
)}
▶ jestliže δ(q, a, Z) obsahuje (r, γ), pak δ′
(q, a, Z) obsahuje (r, γ)
▶ δ′
(q, ε, Z′
) = {(qf , ε)}
pro všechny q ∈ Q
12 / 17
Rozšířený zásobníkový automat
Definice 3.44.
Rozšířený zásobníkový automat je sedmice R = (Q, Σ, Γ, δ, q0, Z0, F),
kde
▶ všechny symboly až na δ mají tentýž význam jako v definici PDA,
▶ δ je zobrazením
z konečné podmnožiny množiny Q × (Σ ∪ {ε}) × Γ∗
do konečných podmnožin množiny Q × Γ∗
.
Pojmy konfigurace a akceptovaný jazyk (koncovým stavem, prázdným
zásobníkem) zůstávají beze změny.
Krok výpočtu | R definujeme takto:
(p, aw, γ1α) | R (q, w, γ2α)
def
⇐⇒ ∃(q, γ2) ∈ δ(p, a, γ1) pro a ∈ Σ∪{ε}
13 / 17
Ekvivalence rozšířených PDA a PDA
Lemma 3.45.
Ke každému rozšířenému PDA existuje ekvivalentní (obyčejný) PDA.
Důkaz. Nechť R = (Q, Σ, Γ, δ, q0, Z0, F) je rozšířený PDA a
m = max{|α| | δ(q, a, α) je definováno pro nějaké q ∈ Q, a ∈ Σ ∪ {ε}}.
14 / 17
Ekvivalence rozšířených PDA a PDA
Lemma 3.45.
Ke každému rozšířenému PDA existuje ekvivalentní (obyčejný) PDA.
Důkaz. Nechť R = (Q, Σ, Γ, δ, q0, Z0, F) je rozšířený PDA a
m = max{|α| | δ(q, a, α) je definováno pro nějaké q ∈ Q, a ∈ Σ ∪ {ε}}.
Definujeme P = (Q1, Σ, Γ1, δ1, q1, Z1, F1), kde
▶ Q1 = {[q, α] | q ∈ Q, α ∈ Γ∗
1, 0 ≤ |α| ≤ m},
▶ Γ1 = Γ ∪ {Z1}, kde Z1 je nový symbol,
▶ q1 = [q0, Z0Zm−1
1 ],
▶ F1 = {[q, α] | q ∈ F, α ∈ Γ∗
1, 0 ≤ |α| ≤ m}.
14 / 17
▶ δ1 je definována takto:
– jestliže δ(q, a, X1 . . . Xk ) obsahuje (r, Y1 . . . Yl ), pak
l < k: δ1([q, X1 . . . Xk α], a, Z) obsahuje ([r, Y1 . . . Yl αZ], ε)
pro všechny Z ∈ Γ1 a α ∈ Γ∗
1 takové, že |α| = m − k
15 / 17
▶ δ1 je definována takto:
– jestliže δ(q, a, X1 . . . Xk ) obsahuje (r, Y1 . . . Yl ), pak
l < k: δ1([q, X1 . . . Xk α], a, Z) obsahuje ([r, Y1 . . . Yl αZ], ε)
pro všechny Z ∈ Γ1 a α ∈ Γ∗
1 takové, že |α| = m − k
l ≥ k: δ1([q, X1 . . . Xk α], a, Z) obsahuje ([r, β], γZ),
kde βγ = Y1 . . . Yl α a |β| = m,
pro všechny Z ∈ Γ1 a α ∈ Γ∗
1 takové, že |α| = m − k
15 / 17
▶ δ1 je definována takto:
– jestliže δ(q, a, X1 . . . Xk ) obsahuje (r, Y1 . . . Yl ), pak
l < k: δ1([q, X1 . . . Xk α], a, Z) obsahuje ([r, Y1 . . . Yl αZ], ε)
pro všechny Z ∈ Γ1 a α ∈ Γ∗
1 takové, že |α| = m − k
l ≥ k: δ1([q, X1 . . . Xk α], a, Z) obsahuje ([r, β], γZ),
kde βγ = Y1 . . . Yl α a |β| = m,
pro všechny Z ∈ Γ1 a α ∈ Γ∗
1 takové, že |α| = m − k
– δ1([q, α], ε, Z) = {([q, αZ], ε)}
pro všechny q ∈ Q, Z ∈ Γ1 a α ∈ Γ∗
1 takové, že |α| < m
15 / 17
Korektnost: Ověříme, že platí
(q, aw, X1 . . . Xk Xk+1 . . . Xn) | R (r, w, Y1 . . . Yl Xk+1 . . . Xn)
⇐⇒ ([q, α], aw, β) |
+
P ([r, α′
], w, β′
),
kde
1. αβ = X1 . . . XnZm
1 ,
2. α′
β′
= Y1 . . . Yl Xk+1 . . . XnZm
1 ,
3. |α| = |α′
| = m a
4. mezi dvěma výše uvedenými konfiguracemi PDA P neexistuje
taková konfigurace, kde druhá komponenta stavu (tj. buffer) by
měla délku m.
16 / 17
Zásobníkové automaty a bezkontextové jazyky
rozšířené
PDA
PDA
akceptující
koncovým
stavem
PDA
akceptující
prázdným
zásobníkem
CFG
Lemma 3.45
triviálně
Věta 3.39
17 / 17
Zásobníkové automaty a bezkontextové jazyky
rozšířené
PDA
PDA
akceptující
koncovým
stavem
PDA
akceptující
prázdným
zásobníkem
CFG
Lemma 3.45
triviálně
Věta 3.39
Ekvivalence CFG a PDA:
Věta 3.47.
Ke každé CFG G lze sestrojit PDA M takový, že L(G) = Le(M).
Idea:
17 / 17
Zásobníkové automaty a bezkontextové jazyky
rozšířené
PDA
PDA
akceptující
koncovým
stavem
PDA
akceptující
prázdným
zásobníkem
CFG
Lemma 3.45
triviálně
Věta 3.39
Ekvivalence CFG a PDA:
Věta 3.47.
Ke každé CFG G lze sestrojit PDA M takový, že L(G) = Le(M).
Idea: větná forma wNα odpovídá přečtení w a zásobníku Nα
jednostavového PDA
Věta 3.51.
Ke každému PDA M lze sestrojit CFG G takovou, že Le(M) = L(G).
Idea:
17 / 17
Zásobníkové automaty a bezkontextové jazyky
rozšířené
PDA
PDA
akceptující
koncovým
stavem
PDA
akceptující
prázdným
zásobníkem
CFG
Lemma 3.45
triviálně
Věta 3.39
Ekvivalence CFG a PDA:
Věta 3.47.
Ke každé CFG G lze sestrojit PDA M takový, že L(G) = Le(M).
Idea: větná forma wNα odpovídá přečtení w a zásobníku Nα
jednostavového PDA
Věta 3.51.
Ke každému PDA M lze sestrojit CFG G takovou, že Le(M) = L(G).
Idea: naopak + redukce vícestavového PDA na jednostavový
17 / 17