W

ykªad

11.

Lemat

o

p

omp

o

w

aniu

dla

jzyk

ó

w

b

ezk

on-

teksto

wy

h

1.

(5

p.)

Udo

w

o

dnij,

»e

jzyk

D

= {a

2

i

: i ≥ 0}

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:

(a)

Demon

wybiera

staª¡

k >

0

.

(b)

W

ybieram

y

sªo

w

o

z

= a

2

k

.

P

oniew

a»

2

k

> k

,

wi

|z| > k

.

( )

Demon

dzieli

sªo

w

o

z

na

sªo

w

a

u

,

v

,

w

,

x

i

y

,

uvwxy

= z

,

przy

zym

vx

6= ε

oraz

|vwx| ≤ k

.

(d)

W

ybieram

y

i

= 2

.

P

oniew

a»

aªe

sªo

w

o

z

skªada

si

t

ylk

o

z

liter

a

,

wi

sªo

w

a

v

,

w

i

x

ró

wnie».

›eb

y

st

wierdzi¢,

zy

sªo

w

o

uv

2

wx

2

y

nale»y

do

jzyk

a

D

,

trzeba

rozstrzygn¡¢

zy

jego

dªugo±¢

jest

p

otg¡

dw

ó

jki.

Zau

w

a»m

y

,

»e

|uv

2

wx

2

y

| = |uvwxy| + |vx| = |z| + |vx| =

2

k

+ |vx|

.

P

onadto,

0 < |vx| ≤ |vwx| ≤ k < 2

k

.

St¡d,

2

k

<

|uv

2

wx

2

y

| < 2

k

+ 2

k

=

2

k+1

.

T

ak

wi

uzysk

ali±m

y

sªo

w

o,

którego

dªugo±¢

nie

jest

p

otg¡

dw

ó

jki,

zyli

gra

k

o« zy

si

nasz¡

wygran¡.

Uzysk

ana

strategia

wygryw

a

j¡ a

do

w

o

dzi,

»e

jzyk

D

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:

(a)

{a

i

b

j

c

k

: 2i + j = k}

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

.

(b)

{a

i

b

j

c

k

: i + j + k = 42}

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

{a

n

b

n

c

n

: n ∈ N}

.

(d)

{a

i

b

j

c

k

: i + 2j = k ∨ 3i + j = 2k}

T

en

jzyk

jest

b

ezk

on

teksto

wy

,

gdy»

jest

sum¡

dw

ó

h

jzyk

ó

w

b

ezk

on

teksto-

wy

h:

{a

i

b

j

c

k

: i + 2j = k}

i

{a

i

b

j

c

k

: i + 2j = k}

.

(e)

{a

n

2

: n ≥ 0}

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