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