1.5. Relacje prawostronnie niezmiennicze

Omawiane w niniejszym podrozdziale relacje zdefiniowane s w zbiorze wszystkich słów nad
pewnym sko czonym alfabetem.

Relacja prawostronnie niezmiennicza
Relacj R

⊆

T*

×

T* (gdzie T jest sko czonym alfabetem symboli) nazywamy prawostronnie

niezmiennicz wtedy i tylko wtedy, gdy

(

∀

u,v

∈

T*) (uRv (

∀

z

∈

T*) uzRvz)

Przykładem relacji prawostronnie niezmienniczej jest relacja R

L

indukowana przez j zyk L

Relacja indukowana przez j zyk
Relacj indukowan przez j zyk L

⊆

T* nazywamy relacj R

L

⊆

T*

×

T* (gdzie T jest

sko czonym alfabetem symboli) tak , e

(

∀

u,v

∈

T*) (uR

L

v

≡

((

∀

z

∈

T*) uz

∈

L

⇔

vz

∈

L))

Uzasadnienie, e relacja R

L

jest relacj prawostronnie niezmiennicz sprowadza si do

pokazania, e je li uR

L

v to dla dowolnego z

∈

T* równie uzR

L

vz. Z definicji relacji R

L

mamy,

e uzR

L

vz wtedy i tylko wtedy, gdy dla dowolnego y

∈

T* zachodzi (uz)y

∈

L

≡

(vz)y

∈

L.

Poniewa zło enie ła cuchów jest operacj ł czn , wi c ostatni zale no mo na zapisa
w postaci u(zy)

∈

L

≡

v(zy)

∈

L. Oznaczaj c zy przez x (x jako zło enie dwóch dowolnych

ła cuchów z T* jest dowolnym ła cuchem nale cym do T*) otrzymamy ux

∈

L

≡

vx

∈

L, co

ko czy uzasadnienie prawostronnej niezmienniczo ci relacji R

L

.

Relacja R

L

indukowana przez j zyk L jest relacj równowa no ci. Zwrotno i symetria

relacji R

L

jest oczywista (czytelnik zechce sprawdzi sam). Uzasadnimy przechodnio relacji

R

L

. Dla dowolnych u,v,w

∈

T* oraz dla dowolnych x,y

∈

T* mamy:

dla uR

L

v zachodzi ux

∈

L

≡

vx

∈

L

dla vR

L

w zachodzi vy

∈

L

≡

wy

∈

L

Poniewa x i y s dowolne, wi c tak e dla dowolnego z

∈

T* jest:

uz

∈

L

≡

vz

∈

L oraz vz

∈

L

≡

wz

∈

L czyli z przechodnio ci równowa no ci uz

∈

L

≡

wz

∈

L.

Wobec tego uR

L

w.

Def. relacji równowa no ci o indeksie sko czonym
Mówimy, e relacja równowa no ci jest relacj o indeksie sko czonym, je eli ta relacja
równowa no ci posiada sko czon liczb klas abstrakcji.

Przykład [Homenda]:
Dany jest j zyk:

{a

m

b

n

c

k

| m+n > 0; n+k > 0}

Znale liczb klas abstrakcji relacji R

L

.

Rozwa ymy nast puj ce zbiory:

• K

0

= {

ε

}

• K

1

= {a

p

| p 1}

• K

2

= {a

p

b

r

| p 0; r 1}

• K

3

= {a

p

b

q

c

r

| p+q 1, r 1}

• K

4

– pozostałe słowa nad alfabetem T = {a, b, c}

Zbiory K

0

, K

1

, K

2

, K

3

, K

4

stanowi podział zbioru wszystkich słów nad alfabetem T = {a,b,c}.

Uzasadnimy, e ka de dwa słowa z dowolnego ze zbiorów K

0

, K

1

, K

2

, K

3

, K

4

pozostaj ze

sob w relacji R

L

:

• K

0

słowo

ε b dzie ze sob w relacji, gdy relacja R

L

jest zwrotna,

• K

1

– dowolne dwa słowa u = a

p

i v = a

q

, gdzie p,q 1, uzupełnione o słowo w

b d nale e do j zyka L wtedy i tylko wtedy, gdy w = a

r

b

s

c

t

, gdzie r 0, s+t 1,

• K

2

– dowolne dwa słowa u=a

k

b

p

i v=a

l

b

q

, gdzie k,l 0, p,q 1, uzupełnione o

słowo w b d nale e do j zyka L wtedy i tylko wtedy, gdy w=b

s

c

t

, gdzie s,t 0

• K

3

– dowolne dwa słowa u=a

p

b

q

c

r

i v=a

k

b

m

c

n

, gdzie p+q 1, r 1, k+m 1,

n 1, uzupełnione o słowo w b d nale e do j zyka L wtedy i tylko wtedy, gdy
w=c

t

, gdzie t 0,

• K

4

– adne słowo z tego zbioru nie b dzie nale e do j zyka po uzupełnieniu go o

dowolne inne słowo.

Wynika st d, e ka dy ze zbiorów K

0

, K

1

, K

2

, K

3

, K

4

zawiera si w pewnej klasie abstrakcji

relacji R

L

. Aby pokaza , e zbiory K

0

, K

1

, K

2

, K

3

, K

4

s klasami abstrakcji nale y jeszcze

udowodni , e adne dwa słowa z ró nych zbiorów nie b d ze sob w relacji R

L

:

• adne słowo z K

0

nie jest w relacji z adnym słowem z K

1

: niech u=

ε

, v=a

p

,

gdzie p 1. Je li w=c, to uw

∉

L, natomiast vw

∈

L,

• adne słowo z K

0

nie jest w relacji z adnym słowem z ka dego ze zbiorów K

2

, K

3

,

K

4

: niech u=

ε

, v – dowolne słowo ze zbiorów K

2

, K

3

, K

4

. Je li

w=abc, to uw

∈

L,

natomiast vw

∉

L.

• adne słowo z K

1

nie jest w relacji z adnym słowem z ka dego ze zbiorów K

2

, K

3

,

K

4

: niech u – dowolne słowo ze zbioru K

1

, v – dowolne słowo ze zbiorów K

2

, K

3

,

K

4

. Je li

w=ab, to uw

∈

L, natomiast vw

∉

L.

• adne słowo z K

2

nie jest w relacji z adnym słowem z ka dego ze zbiorów K

3

, K

4

:

niech u – dowolne słowo ze zbioru K

2

, v – dowolne słowo ze zbiorów K

3

, K

4

. Je li

w=bc, to uw

∈

L, natomiast vw

∉

L.

• adne słowo z K

3

nie jest w relacji z adnym słowem z K

4

: niech u – dowolne słowo

ze zbioru K

3

, v – dowolne słowo ze zbioru K

4

. Je li

w=c, to uw

∈

L, natomiast

vw

∉

L.

Tak wi c liczba klas abstrakcji relacji R

L

wynosi 5.

Przykład
Znale liczb klas abstrakcji relacji R

L

indukowanej przez j zyk:

L = {a

n

b

n

| n 1}

Rozwa ymy jednoelementowe zbiory K

i , j

={a

i

b

j

}, gdzie i=0,1,2,..., za 0

≤

j

≤

i oraz zbiór

K

x

zawieraj cy wszystkie pozostałe słowa nad alfabetem T={a,b}. Zbiory K

i , j

={a

i

b

j

} oraz

zbiór K

x

stanowi podział zbioru wszystkich słów nad alfabetem T={a,b}. Elementy ka dego

ze zbiorów jednoelementowych K

i , j

s oczywi cie w relacji z samymi sob , ze wzgl du na

zwrotno relacji R

L

. Element któregokolwiek ze zbiorów K

i , j

nie jest w relacji z elementem

adnego innego zbioru K

n , m

. Prze led my to na czterech przykładach:

• We my dwa ró ne zbiory K

i , j

={a

i

b

j

}oraz K

i , m

={a

i

b

m

}. Niech u=a

i

b

j

gdzie

0

≤

j

≤

i oraz v=a

i

b

m

gdzie 0

≤

m

≤

i, j

≠

m. Niech w=b

i - j

. Wtedy uw

∈

L, za vw

∉

L.

• We my dwa ró ne zbiory K

i , 0

={a

i

}oraz K

n , m

={a

n

b

m

}. Niech u=a

i

oraz v=a

n

b

m

gdzie 0

≤

m

≤

n, przy czym m

≠

0 lub i

≠

n. Niech w=a

k

b

i + k

. Wtedy uw

∈

L, za

vw

∉

L.

• We my dwa ró ne zbiory K

i , j

={a

i

b

j

}oraz K

n , m

={a

n

b

m

}. Niech u=a

i

b

j

gdzie

0

≤

j

≤

i oraz v=a

n

b

m

gdzie 0

≤

m

≤

n, przy czym j

≠

m lub i

≠

n. Niech w=b

i - j

. Wtedy

uw

∈

L, za vw

∉

L.

• We my dwa ró ne zbiory K

0 , 0

={

ε

}oraz K

n , m

={a

n

b

m

}. Niech u=

ε

oraz v=a

n

b

m

gdzie 0

≤

m

≤

n, przy czym n

≠

0. Niech w=a

k

b

k

, gdzie k>0. Wtedy uw

∈

L, za

vw

∉

L.

aden element zbioru K

x

nie jest w relacji R

L

z elementem któregokolwiek ze zbiorów

jednoelementowych, gdy prawostronne uzupełnienie ka dego z ła cuchów z K

x

o dowolny

ła cuch daje słowo nie b d ce elementem j zyka L, za dla ka dego ze zbiorów
jednoelementowych istnieje jaki ła cuch, po dopisaniu którego z prawej strony do elementu
tego zbioru otrzymamy słowo j zyka. Przykładowo:

• dla zbioru K

0 , 0

zawieraj cego element

ε

b dzie to zbiór ła cuchów {a

j

b

j

| j>0},

• dla zbioru K

i , 0

zawieraj cego element a

i

b dzie to zbiór ła cuchów {a

j

b

i + j

| j 0},

• dla zbioru K

i , i - k

zawieraj cego element a

i

b

i - k

b dzie to ła cuch b

k

,

• dla zbioru K

i , i

zawieraj cego element a

i

b

i

b dzie to ła cuch

ε

.

Tak wi c jednoelementowe zbiory K

i , j

={a

i

b

j

}, gdzie i=0,1,2,...; 0

≤

j

≤

i oraz zbiór K

x

zawieraj cy wszystkie pozostałe słowa nad alfabetem T={a,b} s klasami abstrakcji relacji
R

L

. Liczba klas abstrakcji relacji R

L

jest w tym przypadku niesko czona.