8. cvičení: Pumping lemma pro bezkontextové jazyky, zásobníkové
automaty, nedeterministická syntaktická analýza
Příklad 7.15. Jednu odrážku udělejte pečlivě, v dalších se soustřeďte jen na to podstatné.
Dokažte, že následující jazyky nejsou bezkontextové
a) L = {wcw | w ∈ {a, b}∗
}
b) L = {an
bn
cn
| n ≥ 1}
c) L = {an
bm
cn
dm
| n, m ≥ 1}
Jazyk L = {wcw | w ∈ {a, b}∗
} není bezkontextový
Důkaz. Důkaz vedeme s pomocí obměny lemmatu o vkládání pro bezkontextové jazyky.
Nechť n ∈ N je libovolné, ale nadále pevné. Zvolíme z = an
bn
can
bn
, pak jistě z ∈ L a |z| > n. Uvažujeme
libovolné rozdělení tvaru z = uvwxy, kde |vwx| ≤ n a vx = ε, pro tvar vx mohou nastat následující
případy:
1. vx padle do první poloviny slova, před c, pak stačí zvolit i = 0: jistě odebereme nějaké a nebo b z
první poloviny a tedy výsledek nepatří do L (první část je kratší než druhá)
2. vx padne „přes střed“ slova:
(a) c je podslovem vx: pro volbu i = 0 dostáváme slovo bez c, tedy nepatří do L
(b) jinak, pro volbu i = 0: odebereme nějaká b z první části slova nebo nějaká a z druhé, a tedy
slovo nebude patřit do L, nikdy však nemůže nastat, že bychom odebrali zároveň a z první i
druhé části (nebo b z obou), protože mezi mini je n + 1 jiných znaků a |vwx| ≤ n
3. vx padle do druhé poloviny slova (za c), zvolíme i = 0: druhá část je kratší
Ve všech možných rozděleních jsme dostali uvi
wxi
y /∈ L a tedy L není bezkontextový.
Vysvětlit proč an
can
nestačí (problém v 2b).
Jazyk L = {an
bn
cn
| n ≤ 1} není bezkontextový:
Důkaz. n ∈ N libovolné, volíme z = an
bn
cn
∈ L, je delší než n. Rozdělení z = uvwxy, |vwx| ≤ n, vx = ε:
1. vx padne do aček: i = 0 rozbijeme počet a vzhledem k b
2. vx padne na přelom ab: i = 0 rozbijeme počet a a b vzhledem k c
3. vx padne do bček: i = 0 rozbijeme počet b vzhledem k a
4. vx padle na přelom bc: i = 0 rozbijeme počet b a c vzhledem k a
5. vx padne do cček: i = 0 rozbijeme počet c vzhledem k a
Žádné rozdělení kdy by mohla být všechna 3 písmena v vx není, protože |vwx| ≤ n, tedy máme všechna
rozdělení.
Ve všech případech jsme dostali uvi
wxi
y /∈ L a tedy L není bezkontextový.
Jazyk L = {an
bm
cn
dm
| n, m ≤ 1} není bezkontextový:
Důkaz. n ∈ N libovolné, volíme z = an
bn
cn
dn
∈ L, |z| > n.
Idea: kdykoli tam máme a nebo c tak rozbijeme jejich vztah a kdykoli tam máme b nebo d tak
rozbijeme to, nemůžeme tam mít obojí (a a c, nebo b a d) najednou, protože |vwx| ≤ n. . .
Příklad 8.1. Zmiňte prosím, že byl definován pojem krok výpočtu, ale pojem výpočet pro PDA definován
nebyl. Lze si představit hned několik definic, které kromě zjevných požadavků splňují i tyto:
1. Musí se přečíst celý vstup. V tom případě by v příkladu existoval jen 1 výpočet.
2. Musí se číst „dokud to lze“. V tomto případě existují 4 výpočty.
3. Stačí přečíst libovolnou část vstupu. V tom případě je výpočtů hodně.
Daný ZA A = ({q0, q1, q2, q3, q4}, {a, b, c, d}, {Z, A}, δ, q0, Z, {q4})
δ(q0, a, Z) = {(q0, AZ)} δ(q0, a, A) = {(q0, AA)}
δ(q0, b, A) = {(q1, )} δ(q1, b, A) = {(q1, )}
δ(q1, , A) = {(q2, A), (q3, A)} δ(q2, c, A) = {(q2, )}
δ(q3, d, A) = {(q3, )} δ(q2, , Z) = {(q4, Z)}
δ(q3, , Z) = {(q4, Z)}
• Načrtněte stavový diagram ZA A.
• Naznačte 4 různé výpočty na vstupu a4
b2
c (stačí na obrázku).
• Popište jazyk L(A).
Zásobník se značí s vrcholem vlevo.
stavový diagram, výpočty na a4
b2
c
q0Z q0AZ q0AAZ q0AAAZ q0AAAAZ . . .
q1Z q1AZ q1AAZ q1AAAZ . . .
q2Z q2AZ q2AAZ q2AAAZ . . .
q3Z q3AZ q3AAZ q3AAAZ . . .q4Z
a a a a a
b b b b
b b b b
ε ε ε
c c c c
ε ε ε
d d d d
ε
ε
Intuice k přechodové funkci:
V q0 pod a přidáváme A, pod b se přesuneme do q1 a odebíráme A (musí být alespoň jedno A na zásobníku,
tedy alespoň jedno a přečteno. V q1 čteme b a odebíráme A, nanejvíš o 1 b méně než bylo a, můžeme
přejít bez čtení a změny zásobníku do q2, q3. V q2 čteme c a odebíráme A, tedy načteme nejvýše tolik c
kolik zbývá A na zásobníku, když odstraníme všechna A přejdeme do q4. V q3 totéž jako v q2, jen čteme
d. q4 nečte nic, jen akceptuje (pokud jsme na konci slova). Celkem musí ve slově být alespoň jedno b a
alespoň jedno z c, d, a proto v něm musí být alespoň dvě a.
Tedy L = {an
bk
cn−k
| n1 ≤ k ≤ n − 1} ∪ {an
bk
dn−k
| 1 ≤ k ≤ n − 1}.
Příklad 8.3. Udělejte pořádně aspoň dvě odrážky včetně c). Konstruujte ZA (akceptující koncovým
stavem nebo prázdným zásobníkem) pro jazyky:
a) L = {ai
bj
| i = j, i, j ≥ 0}
b) L = {w | w ∈ {a, b}∗
; w = wR
}
c) L = {a3n
b2n
| n ≥ 1}
d) L = {a3n+2
b2n−1
| n ≥ 1}
e) L = {w | w ∈ {a, b, c}∗
; #a(w) = #b(w)}
f) L = {w | w ∈ {a, b, c}∗
; #a(w) = #b(w)}
g) L = {ak
bj
| 1 ≤ j ≤ k ≤ 2j}
h) L = {an+m
bm+p
cp+n
| m, p, n ≥ 1}
i) L = {ai
bj
cj
| i, j ≥ 1} ∪ {ak
bk
cm
| k, m ≥ 1}
j) L = {ak1
bak2
b . . . bakr
| r > 1, ki ≥ 1 (i = 1, . . . , r; existuje p, s : p = s, kp = ks)}
řešení:
a) A = ({q1, q2, qa, qb}, {a, b}, {Z, A}, δ, q1, Z, {qa, qb}) akceptuje akceptujícím stavem. V q1 načítáme a a
zapamatováváme jejich počet. V q2 načítáme b a odečítáme ze zapamatovaného počtu a. qb je stav
kam se dostaneme, pokud je b více, než a (a můžeme stále přidávat b). qa značí, že a je více než b, ale
protože už jsme mohli načíst nějaká b, nemůžeme načíst další a.
δ(q1, a, Z) = {(q1, AZ)} δ(q2, b, Z) = {(qb, Z)} δ(qb, b, Z) = {(qb, Z)}
δ(q1, a, A) = {(q1, AA)} δ(q2, b, A) = {(q2, ε)}
δ(q1, b, Z) = {(qb, Z)} δ(q2, ε, A) = {(qa, A)}
δ(q1, b, A) = {(q2, ε)}
δ(q1, ε, A) = {(qa, a)}
Bylo by dobré zdůraznit, že automat může obsahovat nedeterminismus i pokud jsou všechny množiny
v přechodech nejvýše jednoprvkové.
c) Budeme na zásobníku počítat ačka. Za každé 3 ačka budeme očekávat 2 bčka, několik řešení:
1. přidat 2 X na zásobník za každé a, odebrat 3 X za každé b
A = ({qa, qb, q2X, q1X}, {a, b}, {Z, X}, δ, qa, Z, ∅)
akceptuje prázdným zásobníkem
δ(qa, a, Z) = {(qa, XXZ)} δ(qb, b, X) = {(q2X, ε)}
δ(qa, a, X) = {(qa, XXX)} δ(q2X, ε, X) = {(q1X, ε)}
δ(qa, b, X) = {(q2X, ε)} δ(q1X, ε, X) = {(qb, ε)}
δ(qb, ε, Z) = {(qb, ε)}
Poznáka: Zásobníkový automat (nerozšířený) nemůže přečíst, a tedy ani smazat, více než 1 znak
ze zásobníku v jednom kroku, proto potřebujeme pomocné stavy q2X a q1X které slouží jen k
odmazání dalších 2 X ze zásobníku.
2. přidat 2 X na zásobník za každé 3 a, odebrat 1 za b
3. přidat 1 X na zásobník za každá 3 a, odebrat 1 za každá 2 b (ukončit načítání aček a začít s bčky
pak umožníme jen pokud je počet a dělitelný 3 a zároveň jsme již viděli nějaká ačka)
A = ({qa0, qa1, qa2, qb0, qb1, qacc}, {a, b}, {Z, X}, δ, qa0, Z, {qacc})
Akceptuje akceptujícím stavem.
δ(qa0, a, Z) = {(qa1, Z)} δ(qb0, b, A) = {(qb1, A)}
δ(qa0, a, A) = {(qa1, A)} δ(qb1, b, A) = {(qb0, ε)}
δ(qa1, a, Z) = {(qa2, Z)} δ(qb0, ε, Z) = {(qacc, ε)}
δ(qa1, a, A) = {(qa2, A)}
δ(qa2, a, Z) = {(qa0, AZ)}
δ(qa2, a, A) = {(qa0, AA)}
δ(qa0, b, A) = {(qb1, A)}
Příklad 8.6. Analýzu provádějte na slově ababaa.
Pro danou G navrhněte (rozšířený) ZA, který provádí syntaktickou analýzu:
a) shora dolů,
b) zdola nahoru.
V obou případech proveďte analýzu slova ababaa.
G = ({S, A, B},{a, b},P, S), kde
P = { S → | abSA,
A → AaB | aB | a,
B → aSS | bA }
Shora dolů
• simuluje levou derivaci
• jediný stav q, akceptuje prázdným zásobníkem
• zásobníková abeceda jsou terminály i neterminály gramatiky
• za každé pravidlo tvaru A → α v gramatice přidáme (q, α) do δ(q, ε, A)
• pro každý terminál a ∈ Σ přidáme přechod δ(q, a, a) = {(q, ε)}
• začínáme s kořenovým neterminálem na zásobníku
• gramatika střídavě „expanduje pravidla na zásobníku“ a „kontroluje, že písmeno na vrcholu zásobníku
sedí se vstupem“
M = ({q}, {a, b}, {a, b, S, A, B}, δ, q, S, ∅)
akceptuje prázdným zásobníkem
δ(q, ε, S) = {(q, ε), (q, abSA)} δ(q, a, a) = {(q, ε)}
δ(q, ε, A) = {(q, AaB), (q, aB), (q, a)} δ(q, b, b) = {(q, ε)}
δ(q, ε, B) = {(q, aSS), (q, bA)}
Analýza ababaa:
Nejprve vytvoříme derivační strom:
S
a b S
a b S A
a
A
a
Analyzátor shora dolů bude realizovat levou derivaci, tedy
S ⇒ abSA ⇒ ababSAA ⇒ ababAA ⇒ ababaA ⇒ ababaa
Pravidla tedy musíme na zásobníku expandovat v tomto pořadí (je však možné expandovat neterminál
jedině pokud se nachází na vrcholu zásobníku, jinak musíme číst ze vstupu a tím „zkontrolovat“ terminál
na zásobníku).
(q, ababaa, S)
ε
S→abSA (q, ababaa, abSA)
a
(q, babaa, bSA)
b
(q, abaa, SA)
ε
S→abSA (q, abaa, abSAA)
a
(q, baa, bSAA)
b
(q, aa, SAA)
ε
S→ε (q, aa, AA)
ε
A→a (q, aa, aA)
a
(q, a, A)
ε
A→a (q, a, a)
a
(q, ε, ε)
Akceptovali jsme. Symboly na odvozovací relaci jsou jen pomocné, nahoře uvádíme znak vstupu, který
se načetl, dole případné pravidlo, jehož expanze proběhla.
Zdola nahoru
• simuluje pravou derivaci v obráceném pořadí
• rozšířený PDA, zásobník píšeme obráceně (vrchol vpravo)
• zásobníková abeceda jsou terminály, neterminály a speciální symbol ⊥ umožňující nám poznat dno
zásobníku
• má dva stavy q, kde probíhá výpočet, a r, který slouží jen k akceptování
• pro každý terminál a ∈ Σ přidáme do přechodové funkce δ(q, a, ε) = {(q, a)}
• pro každé pravidlo A → α přidáme do δ(q, ε, α) dvojici (q, A)
• speciální pravidlo δ(q, ε, ⊥S) = {(r, ε)} slouží k akceptování (pokud vstup nebyl dočten automat se
zasekne)
• automat střídavě „přesouvá znaky ze vstupu na zásobník“ a „provádí redukci pravidel gramatiky
na zásobníku z jejich pravé strany na levou“
R = ({q, r}, {a, b}, {a, b, S, A, B, ⊥}, δ, q, ⊥, {r})
Rozšířený PDA akceptuje vždy akceptujícím stavem. Pozor, vrchol zásobníku je v analýze zdola nahoru
otočen vpravo.
δ(q, ε, ε) = {(q, S)} δ(q, a, ε) = {(q, a)}
δ(q, ε, abSA) = {(q, S)} δ(q, b, ε) = {(q, b)}
δ(q, ε, AaB) = {(q, A)} δ(q, ε, ⊥S) = {(r, ε)}
δ(q, ε, aB) = {(q, A)}
δ(q, ε, a) = {(q, A)}
δ(q, ε, aSS) = {(q, B)}
δ(q, ε, bA) = {(q, B)}
Pravidla redukují větnou formu na zásobníku. Pokud se nějaká pravá strana v gramatice objevuje opakovaně,
pak jí musí odpovídat jedno pravidlo s více možnostmi přechodu.
Analýza ababaa:
Nejprve vytvoříme derivační strom:
S
a b S
a b S A
a
A
a
Ze stromu odvodíme, že pravá derivace našeho slova je
S ⇒ abSA ⇒ abSa ⇒ ababSAa ⇒ ababSaa ⇒ ababaa
Analyzátor bude tuto derivaci realizovat v opačném pořadí a to vždy na vrcholu zásobníku (tj. například
S → ε musíme provést v okamžiku, kdy máme načtené abab, protože S touto redukcí přidáme na vrchol
zásobníku).
(q, ababaa, ⊥)
a
(q, babaa, ⊥a)
b
(q, abaa, ⊥ab)
a
(q, baa, ⊥aba)
b
(q, aa, ⊥abab)
ε
S→ε (q, aa, ⊥ababS)
a
(q, a, ⊥ababSa)
ε
A→a (q, a, ⊥ababSA)
ε
S→abSA (q, a, ⊥abS)
a
(q, ε, ⊥abSa)
ε
A→a (q, ε, ⊥abSA)
ε
S→abSA (q, ε, ⊥S)
ε
acc (r, ε, ε)
Akceptovali jsme. Opět platí, že symboly na odvozovací relaci jsou jen pomocné, nahoře uvádíme znak
vstupu, který se načetl, dole případné pravidlo, jehož redukce proběhla.