W
ykªad
11.
Lemat
o
p
omp
o
w
aniu
dla
jzyk
ó
w
b
ezk
on-
teksto
wy
h
D = {a2i : i ≥ 0}
1.
(5
p.)
Udo
w
o
dnij,
»e
jzyk
nie
jest
b
ezk
on
teksto
wy
.
Do
w
ó
d
przepro
w
adzam
y
k
orzysta
j¡
ze
sform
uªo
w
ania
lematu
o
p
omp
o
w
aniu,
jak
o
gry
z
demonem.
Oto
strategia
wygryw
a
j¡ a:
k > 0
(a)
Demon
wybiera
staª¡
.
z = a2k
2k > k
|z| > k
(b)
W
ybieram
y
sªo
w
o
.
P
oniew
a»
,
wi
.
z
u v w x
y uvwxy = z vx 6= ε
( )
Demon
dzieli
sªo
w
o
na
sªo
w
a
,
,
,
i
,
,
przy
zym
|vwx| ≤ k
oraz
.
i = 2
(d)
W
ybieram
y
.
z
a
v w
x
P
oniew
a»
aªe
sªo
w
o
skªada
si
t
ylk
o
z
liter
,
wi
sªo
w
a
,
i
ró
wnie».
eb
y
uv2wx2y
D
st
wierdzi¢,
zy
sªo
w
o
nale»y
do
jzyk
a
,
trzeba
rozstrzygn¡¢
zy
jego
|uv2wx2y| = |uvwxy| + |vx| = |z| + |vx| =
dªugo±¢
jest
p
otg¡
dw
ó
jki.
Zau
w
a»m
y
,
»e
2k + |vx|
0 < |vx| ≤ |vwx| ≤ k < 2k 2k < |uv2wx2y| < 2k + 2k =
.
P
onadto,
.
St¡d,
2k+1. Tak wi uzyskali±my sªowo, którego dªugo±¢ nie jest potg¡ dwójki, zyli gra
k
o« zy
si
nasz¡
wygran¡.
D
Uzysk
ana
strategia
wygryw
a
j¡ a
do
w
o
dzi,
»e
jzyk
nie
jest
b
ezk
on
teksto
wy
.
2.
(5
p.)
Dla
k
a»dego
z
p
oni»szy
h
jzyk
ó
w
okre±l,
zy
jest
on:
(i)
regularn
y
,
(ii)
b
ez-
k
on
teksto
wy
,
ale
nie
regularn
y
,
(iii)
nie
jest
b
ezk
on
teksto
wy:
{aibjck : 2i + j = k}
(a)
T
en
jzyk
jest
b
ezk
on
teksto
wy
.
Generalnie, je»eli
w
deni ji
jzyk
a
wystpuje
jedna
zale»no±¢
linio
w
a
dot
y z¡ a
ilo± i
liter,
to
taki
jzyk
jest
b
ezk
on
teksto
wy
.
{aibjck : i + j + k = 42}
(b)
T
en
jzyk
jest
regularn
y
,
gdy»
jest
sk
o« zon
y
.
{w ∈ {a, b, c}∗ : #a(w) = #b(w) = #c(w)}
( )
T
en
jzyk
nie
jest
b
ezk
on
teksto
wy
.
Do
w
ó
d
przebiega
p
o
dobnie
jak
dla
jzyk
a
{anbncn : n ∈ N}.
{aibjck : i + 2j = k ∨ 3i + j = 2k}
(d)
T
en
jzyk
jest
b
ezk
on
teksto
wy
,
gdy»
jest
sum¡
dw
ó
h
jzyk
ó
w
b
ezk
on
teksto-
{aibjck : i + 2j = k} {aibjck : i + 2j = k}
wy
h:
i
.
{an2 : n ≥ 0}
(e)
T
en
jzyk
nie
jest
b
ezk
on
teksto
wy
.
Mo»na
to
p
ok
aza¢
k
orzysta
j¡
z
lematu
o
p
omp
o
w
aniu.
15