Pumping lemma pro bezkontextové jazyky
V kapitole 9.5 CFG v Chomského normální formě jsme naznačili, že CNF je kanonický tvar,
který významně použijeme v dokazování pomocí Pumping lemmatu pro bezkontextové jazyky.
Ještě než si uvedeme znění lemmatu, vysvětlíme, proč oba zmíněné pojmy spolu souvisejí.
Věta 1.
Nechť G = (N, Σ, P, S) je bezkontextová gramatika v Chomského normální formě, w ∈ L(G)
je libovolné slovo. Označme derivační strom pro slovo w symbolem T . Pak platí tvrzení: má-li
každá cesta ve stromu T délku maximálně n (n ∈ N), pak T obsahuje nejvýše 2n−1
listů.
Poznámka.
Ještě než provedeme důkaz, ukážeme si několik konkrétních případů derivačního stromu pro
libovolné slovo w ∈ L(G), kde G je CFG v Chomského normální formě.
1. Začneme stromem, kde libovolná cesta má délku maximálně 1 (tj. n = 1). Uvědomte si,
že v tom případě vypadá strom tak, že obsahuje pouze kořen, z něhož vede jediná cesta
k listu. Počet listů je tedy 1 = 2n−1
= 21−1
= 20
.
2. Je-li n maximálně 2, tj. libovolná cesta ve stromu je délky nejvýše 2 (n ≤ 2), pak máme
opět jedinou možnost, jak strom může vypadat (nepočítáme-li situaci z 1. případu). Z kořene
A vedou dvě cesty do vnitřních uzlů B, C ∈ N (dle pravidla A → BC) a z každého
z nich potom jedna cesta do listu (dle pravidel B → x, C → y, kde x, y jsou libovolné
terminály). Počet listů je 2, což opět odpovídá podmínce věty, že má být nejvýše
2n−1
= 22−1
= 2.
3. Je-li n maximálně 3, pak libovolná cesta ve stromu má délku nejvýše 3 (n ≤ 3). V tu chvíli
už máme tři možné situace, jak strom může vypadat. Pro lepší přehlednost označíme listy
čtvercem a vnitřní uzly kružnicí:
a) b) c)
Všimněte si, že nejvyšší počet listů je v případě a), a to 4. Týká se to situace, kdy každá
cesta ve stromu má délku právě 3. Je tedy zřejmé, že největší počet listů ve stromu, jehož
libovolná cesta má délku max. 3, je v případě, že každá cesta má délku 3. V ostatních
případech (b, c) je počet listů menší než 4. I zde tedy platí závěr věty: počet listů je max.
4 = 2n−1
= 23−1
= 22
.
Takto bychom mohli pokračovat dále. Místo toho však podáme obecný důkaz věty pro libovolné
n ∈ N znamenající max. možnou délku cesty ve stromu.
1
Důkaz. Nechť platí předpoklady věty, tj. mějme bezkontextovou gramatiku G = (N, Σ, P, S)
v Chomského normální formě. Zvolme slovo w ∈ L(G) libovolně a označte symbolem T jeho
derivační strom. Dále předpokládejme, že každá cesta ve stromu T má délku maximálně n.
Uvažujme podstrom T1 stromu T , který vznikne tak, že ze stromu T odstraníme listy a cesty
do nich. Pro takový strom platí, že délka jeho libovolné cesty je nejvýše n − 1.
Předpokládejme navíc striktně, že
(∗) každá cesta ve stromu T1 má délku právě n − 1.
(Je to případ, kdy strom T1 může mít nejvíce listů.) Protože T1 vznikl z derivačního stromu
T vyjmutím jeho listů, platí, že každý vnitřní uzel T1 má právě dva následníky (mohli jsme
použít pouze pravidla A → BC). To znamená, že kořen má 2 přímé následníky (1. díl cesty), 4
následníky ve 2. úrovni „pod kořenem (2. díl cesty), ..., 2n−1
následníků v (n − 1)-té úrovni
„pod kořenem [(n − 1)-tý díl cesty]. Z toho vyplývá, že počet listů stromů T1 je právě 2n−1
.
Připojíme-li ke stromu T1 původní listy stromu T , zjišťujeme, že jejich počet je také 2n−1
.
Protože jsme v předpokladu (*) počítali s tím, že délka každé cesty ve stromu T1 je právě
n − 1, úpravou (*)
(∗∗) každá cesta ve stromu T1 má maximálně n − 1
zajistíme tvrzení věty, tj. že počet listů stromu T1, potažmo T je nejvýše 2n−1
.
Lemma (Věta o vkládání – Pumping lemma)
Buď L bezkontextový jazyk.
Pak existují p, q ∈ N takové, že každé slovo w ∈ L, |w| > p, lze psát ve tvaru w = uvwxy tak,
že:
a) alespoň jedno ze slov v, x je neprázdné (v, x = ε),
b) |vwx| ≤ q,
c) pro každé i ∈ N0 platí uvi
wxi
y ∈ L.
Poznámka.
1. Konstanta p se může rovnat q.
2. Tvrzení je ve tvaru P ⇒ Q, kde
• P je předpoklad, že L je bezkontextový jazyk, a
• Q je zbytek tvrzení, tj. že existují konstanty p, q ∈ N0 takové, že...
3. V případě, že Q platí, nelze říci, jestli platí či neplatí P (tj. zda L je či není bezkontextový
jazyk, protože implikace 0 ⇒ 1 nebo 1 ⇒ 1 jsou obě pravdivé).
Pokud ale předpokládáme, že P platí (tj. L je bezkontextový) a dokážeme ¬Q, pak je
platnost P ∧ ¬Q ve sporu s Pumping lemmatem, protože jsme ukázali pravdivost
¬(P ⇒ Q) = P ∧ ¬Q. Náš předpoklad, že P platí, není správně, a tudíž P neplatí (tedy
jazyk L není bezkontextový).
4. Z předchozího bodu vyplývá, že Pumping lemma lze použít pouze k důkazu toho, že daný
jazyk L není bezkontextový.
2
Důkaz Pumping lemmatu. Předpokládejme, že L je bezkontextový jazyk. Potom existuje
bezkontextová gramatika G = (N, Σ, P, S), která jazyk L generuje, tj. L = L(G). Bez újmy
na obecnosti předpokládejme, že G je v Chomského normální formě. Položme k rovno počtu
neterminálů, p = 2k−1
, q = 2k
.
Zvolme slovo z ∈ L takové, že |z| > p = 2k−1
. Tedy derivační strom pro z má více než
2k−1
listů. Potom (dle věty 1 na začátku tohoto dokumentu) existuje v derivačním stromu pro
z cesta delší než k. Počet vnitřních uzlů cesty je tedy větší než k, což znamená, že minimálně
jeden neterminál se v derivační cestě musí opakovat.
Zvolme pevně derivační strom T pro slovo z a v něm cestu c delší než k, která zároveň
bude nejdelší možná. [Předpoklad maximální možné délky cesty c je pro nás v další fázi důkazu
důležitý!]
Na cestě c lze zvolit tři uzly u1, u2, u3 s těmito vlastnostmi:
1. uzly u1, u2 jsou označeny tím samým neterminálem A,
2. u1 je blíže ke kořeni než u2,
3. uzel u3 je list,
4. cesta od u1 do u3 má délku nejvýše k + 1.
A
A
list
S
u v w x y
c
c
c
Uzel u1 označený neterminálem A určuje strom T1 (u1 je kořenem T1). Protože T1 je podstromem
T , musí existovat slova u, y a derivace
(1) S ⇒∗
uAy
Uzel u2 označený taktéž neterminálem A určuje strom T2, přičemž platí, že T2 je podstromem
T1. Z toho opět vyplývá, že existují řetězce v, x a derivace
(2) A ⇒∗
vAx
3
Výsledkem podstromu T1 je nějaké slovo z1, které je podslovem slova z. Dle vlastnosti 4 má
podstrom T1 nejvýše 2k
listů (opět to vyplývá z Věty 1). To znamená, že i délka slova
|z1| ≤ 2k
= q. Pokud by existovala cesta z uzlu u1 k nějakému jinému listu u4, která by byla
delší než k + 1, pak by to byl spor s předpokladem, že naše cesta c je nejdelší.
Výsledkem podstromu T2 je nějaké slovo w, pro které platí, že je podslovem slova z1. Zároveň
jistě existuje derivace tvaru
(3) A ⇒∗
w
Nyní použijme jedenkrát derivaci (1), i-krát derivaci (2) a nakonec jedenkrát derivaci (3):
(4) S ⇒∗
uAy ⇒∗
uvi
Axi
y ⇒∗
uvi
wxi
y
Z derivace (4) je patrné, že slovo uvi
wxi
y ∈ L(G) (bod c je dokázán).
Navíc v předchozím jsme tvrdili, že pokud cestu z uzlu u1 do listu u3 uskutečníme jednou,
bude mít podstrom T1 příslušný uzlu u1 maximálně 2k
= q listů. Výsledkem stromu T1 je slovo
z1, potažmo vwx, jehož délka je menší nebo rovna q = 2k
(bod b dokázán).
Dále si uvědomme, že uzel u1 s návěštím A je vnitřní uzel, tj. musí existovat derivace
A ⇒ BC. Gramatika G je v Chomského normální formě, tj. bez ε-pravidel, musí tedy platit,
že alespoň jeden z neterminálů B, C se odvodí na neprázdné slovo. Díky tomu můžeme psát
vx = ε (bod a je dokázán).
Tím je důkaz hotov.
Poznámka.
Raději si uvedeme přesné znění negace tvrzení Q: pro všechna p, q ∈ N0 existuje slovo
w ∈ L, |w| > p, tak, že pro každé možné rozdělení slova z = uvwxy, kde
a) vx = ε a zároveň
b) |vwx| ≤ q,
platí, že existuje i ∈ N0 tak, že uvi
wxi
y /∈ L.
Poznámka.
Mějme libovolný jazyk L, u kterého chceme ukázat, že není bezkontextový. Nejjednodušší strategie
důkazu pomocí Pumping lemmatu spočívá v tom, že volíme slovo z ∈ L(G) závislé pouze
na jediné obecně zadané konstantě n ∈ N0. Tj. platí n = p = q. Nemůžeme však zvolit nějaké
konkrétní slovo, protože potom bychom nesplnili počáteční podmínku tvrzení ¬Q: pro všechna
p, q ∈ N0..., respektive pro všechna n ∈ N0... Zároveň by u naší volby slova z mělo platit, že
|z| > n.
Poté hledáme všechna možná rozdělení slova z na pět částí u, v, w, x, y, přičemž klademe
důležitou podmínku: |vwx| ≤ n. Pro každé rozdělíme hledáme konkrétní konstantu i ∈ N0 tak,
abychom zajistili uvi
wxi
y /∈ L. Podaří-li se nám to pro všechna rozdělení, pak jsme ukázali
platnost ¬Q, což spolu s předpokladem P (jazyk L je bezkontextový) zajišťuje spor s Pumping
lemmatem. Toto lemma je však dokázáno, je tedy chyba v našem předpokladu P, a proto platí
jeho opak. Jazyk L není bezkontextový.
4