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 RL indukowana przez j zyk L

Relacja indukowana przez j zyk

Relacj indukowan przez j zyk L ⊆ T* nazywamy relacj RL ⊆ T* × T* (gdzie T jest

sko czonym alfabetem symboli) tak , e

(∀ u,v∈ T*) (uRLv ≡ ((∀ z∈ T*) uz∈ L ⇔ vz∈ L))

Uzasadnienie, e relacja RL jest relacj prawostronnie niezmiennicz sprowadza si do

pokazania, e je li uRLv to dla dowolnego z∈ T* równie uzRLvz. Z definicji relacji RL mamy,

e uzRLvz 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 RL.

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

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

RL. Dla dowolnych u,v,w ∈ T* oraz dla dowolnych x,y ∈ T* mamy:

dla uRLv zachodzi ux∈ L ≡ vx∈ L

dla vRLw 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 uRLw.

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:

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

Znale liczb klas abstrakcji relacji RL.

Rozwa ymy nast puj ce zbiory:

• K0 = {ε }

• K1 = {ap | p 1}

• K2 = {apbr | p 0; r 1}

• K3 = {apbqcr | p+q 1, r 1}

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

Zbiory K0, K1, K2, K3, K4 stanowi podział zbioru wszystkich słów nad alfabetem T = {a,b,c}.

Uzasadnimy, e ka de dwa słowa z dowolnego ze zbiorów K0, K1, K2, K3, K4 pozostaj ze

sob w relacji RL:

• K0 słowo ε b dzie ze sob w relacji, gdy relacja RL jest zwrotna,

• K1 – dowolne dwa słowa u = ap i v = aq, gdzie p,q 1, uzupełnione o słowo w

b d nale e do j zyka L wtedy i tylko wtedy, gdy w = arbsct, gdzie r 0, s+t 1,

• K2 – dowolne dwa słowa u=akbp i v=albq, 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=bsct, gdzie s,t 0

• K3 – dowolne dwa słowa u=apbqcr i v=akbmcn, 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=ct, gdzie t 0,

• K4 – 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 K0, K1, K2, K3, K4 zawiera si w pewnej klasie abstrakcji

relacji RL. Aby pokaza , e zbiory K0, K1, K2, K3, K4 s klasami abstrakcji nale y jeszcze

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

• adne słowo z K0 nie jest w relacji z adnym słowem z K1: niech u=ε , v=ap,

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 K2, K3,

K4: niech u=ε , v – dowolne słowo ze zbiorów K2, K3, K4. 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 K2, K3,

K4: niech u – dowolne słowo ze zbioru K1, v – dowolne słowo ze zbiorów K2, K3,

K4. 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 K3, K4:

niech u – dowolne słowo ze zbioru K2, v – dowolne słowo ze zbiorów K3, K4. 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 K4: niech u – dowolne słowo

ze zbioru K3, v – dowolne słowo ze zbioru K4. Je li w=c, to uw∈ L, natomiast

vw∉ L.

Tak wi c liczba klas abstrakcji relacji RL wynosi 5.

Przykład

Znale liczb klas abstrakcji relacji RL indukowanej przez j zyk:

L = {anbn | n 1}

Rozwa ymy jednoelementowe zbiory Ki,j={aibj}, gdzie i=0,1,2,..., za 0≤ j≤ i oraz zbiór

Kx zawieraj cy wszystkie pozostałe słowa nad alfabetem T={a,b}. Zbiory Ki,j={aibj} oraz

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

ze zbiorów jednoelementowych Ki,j s oczywi cie w relacji z samymi sob , ze wzgl du na

zwrotno relacji RL. Element któregokolwiek ze zbiorów Ki,j nie jest w relacji z elementem

adnego innego zbioru Kn,m. Prze led my to na czterech przykładach:

• We my dwa ró ne zbiory Ki,j={aibj} oraz Ki,m={aibm}. Niech u=aibj gdzie

0≤ j≤ i oraz v=aibm gdzie 0≤ m≤ i, j≠ m. Niech w=bi-j. Wtedy uw∈ L, za vw∉ L.

• We my dwa ró ne zbiory Ki,0={ai} oraz Kn,m={anbm}. Niech u=ai oraz v=anbm

gdzie 0≤ m≤ n, przy czym m≠ 0 lub i≠ n. Niech w=akbi+k. Wtedy uw∈ L, za vw∉ L.

• We my dwa ró ne zbiory Ki,j={aibj} oraz Kn,m={anbm}. Niech u=aibj gdzie

0≤ j≤ i oraz v=anbm gdzie 0≤ m≤ n, przy czym j≠ m lub i≠ n. Niech w=bi-j. Wtedy uw∈ L, za vw∉ L.

• We my dwa ró ne zbiory K0,0={ε } oraz Kn,m={anbm}. Niech u=ε oraz v=anbm

gdzie 0≤ m≤ n, przy czym n≠ 0. Niech w=akbk, gdzie k>0. Wtedy uw∈ L, za vw∉ L.

aden element zbioru Kx nie jest w relacji RL z elementem któregokolwiek ze zbiorów

jednoelementowych, gdy prawostronne uzupełnienie ka dego z ła cuchów z Kx 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 {ajbj | j>0},

• dla zbioru K i,0 zawieraj cego element ai b dzie to zbiór ła cuchów {ajbi+j | j 0},

• dla zbioru K i,i-k zawieraj cego element aibi-k b dzie to ła cuch bk,

• dla zbioru K i,i zawieraj cego element aibi b dzie to ła cuch ε .

Tak wi c jednoelementowe zbiory Ki,j={aibj}, gdzie i=0,1,2,...; 0≤ j≤ i oraz zbiór Kx

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

RL. Liczba klas abstrakcji relacji RL jest w tym przypadku niesko czona.