Pumping
l
emma: Apli
k
a
ce
15
/31
•
Pomocí pumping lemmy pro BKJ často provádíme
důkaz sporem, že daný jazyk
není
bezkontextový:
Předpokládejme, že
L
je bezkontextový
Uvažujme
PL
konstantu
k
a
vyberme
z
Î
L
,
jehož
délka je závislá na
k
tak,
že
|z|
³
k
je vždy pravdivé
Pro
všechny
dekompozice
z
na
uvwxy
:
vx
¹
ε
,
|
vwx
|
£
k
,
ukážeme:
existuje
m
³
0
pro které
uv
m
wx
m
y
Ï
L
;
ale podle PL platí vztah:
uv
m
wx
m
y
Î
L
SPOR
špatný předpoklad
Proto
L
není bezkontextový