W

ykªad

7.

Lemat

o

p

omp

o

w

aniu

dla

jzyk

ó

w

regularn

y

h

1.

(2

p.)

Które

z

p

oni»szy

h

jzyk

ó

w

s¡

regularne,

a

które

nie?

(Odp

o

wiedzi

nie

m

usisz

formalnie

uzasadnia¢.)

a)

{a

n

3

: n ≥ 0}

Nie

jest

regularn

y

.

Mo»na

zastoso

w

a¢

lemat

o

p

omp

o

w

aniu.

b)

{a

i

b

j

: i · j ≤ 42}

Jest

regularn

y

,

gdy»

jest

sum¡

jzyk

a

sk

o« zonego,

oraz

jzyk

ó

w

L

(a

∗

)

i

L

(b

∗

)

.

)

{a

i

b

j

: i ≡ j

mo

d

42}

Jest

regularn

y

,

do

spra

wdzenia

zy

sªo

w

o

nale»y

do

tego

jzyk

a

wystar zy

li znik

mo

dulo

42

(tzn.

mo»na

sk

onstruo

w

a¢

automat

sk

o« zon

y

ak

eptuj¡ y

ten

jzyk,

o

84

stana

h).

d)

{ww : w ∈ {a, b}

∗

}

Nie

jest

regularn

y

.

Mo»na

zastoso

w

a¢

lemat

o

p

omp

o

w

aniu.

e)

{a

n

b

m

: |n − m| ≤ 42}

Nie

jest

regularn

y

.

Mo»na

zastoso

w

a¢

lemat

o

p

omp

o

w

aniu,

dla

i

≥ 85

.

2.

(4

p.)

P

ok

a»,

»e

jzyk

{a

m

b

n

a

m·n

: m, n ≥ 0}

nie

jest

regularn

y

.

Stosujem

y

lemat

o

p

omp

o

w

aniu,

np.

sform

uªo

w

an

y

jak

o

gra

z

Demonem.

Demon

wybiera

k

.

W

e¹m

y

sªo

w

a

p

osta i

x

= a

,

y

= b

k

,

z

= a

k

,

xyz

= ab

k

a

k

.

Demon

dzieli

sªo

w

o

y

na

trzy

z± i

x

= uvw

,

v

6= ε

.

Jakk

olwiek

b

y

ten

p

o

dziaª

nie

wygl¡daª,

to

sªo

w

o

v

skªada

si

z

liter

b

.

W

ybieram

y

i

= 2

.

Sªo

w

o

xuv

i

wz

nie

nale»y

do

rozpatryw

anego

jzyk

a,

gdy»

jest

w

nim

wi ej

liter

b

,

ni»

nastpuj¡ y

h

p

o

ni

h

liter

a

.

T

ak

wi ,

jest

to

opis

strategii

wygryw

a

j¡ ej.

St¡d,

rozpatryw

an

y

jzyk

nie

jest

regularn

y

.

3.

(4

p.)

P

ok

a»,

»e

jzyk

za

wiera

j¡ y

te

sªo

w

a

nad

alfab

etem

{a, b}

,

które

za

wiera

j¡

t

yle

samo

liter

a

i

b

,

{x ∈ {a, b}

∗

: #

a

(x) = #

b

(x)}

,

nie

jest

regularn

y

.

Do

w

o

dzim

y

tego

nie

wprost.

Zaªó»m

y

prze iwnie,

»e

jest

regularn

y

.

Wó

w

zas,

z

faktu,

»e

klasa

jzyk

ó

w

regularn

y

h

jest

domknita

na

prze i ie

jzyk

ó

w

wynik

a,

»e

jzyk

{x ∈ {a, b}

∗

: #

a

(x) = #

b

(x)} ∩ L(a

∗

b

∗

) = {a

n

b

n

: n ≥ 0}

jest

regularn

y

.

Jednak

na

wykªadzie

p

ok

azano,

»e

nie

jest

on

regularn

y



sprze zno±¢.

St¡d,

dan

y

jzyk

nie

mo»e

b

y¢

regularn

y

.

10