Edward Ochmański Warszawa, 27. 11. 1995



Pobieranie 50,88 Kb.
Data23.10.2017
Rozmiar50,88 Kb.

LINGWISTYKA WSPÓŁBIEŻNOŚCI

Lekcja 2 Monoidy

2.1 MONOID, MONOID POTĘGOWY, OPERACJA ITERACJI

Monoid (M,) to zbiór M z binarną operacją złożenia, spełniającą następujące warunki:

(1) Operacja złożenia nie wyprowadza poza zbiór M:


(x,yM) xyM

(1) Operacja złożenia jest łączna:


(x,y,zM) (xy)z=x(yz)

(2) Istnieje element neutralny, zwany jedynką i oznaczany 1:


(1M) (xM) 1x=x=x1

Fakt: Każdy monoid ma dokładnie jedną jedynkę.
Dowód: Jeśli 1 i 1 są jedynkami, to są one równe, bo 1=11=1.

Monoid potęgowy monoidu (M,) to monoid P(M)=(2M,), gdzie:

(1) 2M jest zbiorem wszystkich podzbiorów (czyli zbiorem potęgowym) zbioru M

(2) Operacja  (złożenie zbiorów) w P(M) jest rozszerzeniem operacji złożenia w M do operacji na podzbiorach: XY={xy | xX  yY}

(3) Jedynką w P(M) jest singleton {1}, gdzie 1 jest jedynką w M.



Umowa: Zawsze, gdy nie będzie to prowadziło do nieporozumień, będziemy pisać i mówić „monoid M” zamiast „monoid (M,)”. Prawie zawsze będziemy też pomijać znak operacji złożenia, czyli będziemy pisać „xy” zamiast „xy”.

Operacje w monoidzie potęgowym: W zbiorze 2M wszystkich podzbiorów monoidu M mamy, oczywiście, określone klasyczne operacje na zbiorach: suma , przecięcie  i różnica . Wyżej określiliśmy operację złożenia zbiorów w 2M, indukowaną przez operację złożenia w M. Operacja potęgowania to właściwie skrócony zapis pewnych przypadków operacji złożenia. Mianowicie:

Dla XM określamy: X0={1} Xn+1= XXn

Teraz jesteśmy gotowi do zdefiniowania operacji iteracji, operacji niezwykle ważnej, nie tylko w teorii języków formalnych czy teorii monoidów. Zwana jest ona również operacją „gwiazdki”, „gwiazdką Kleene’go” bądź „domknięciem Kleene’go”.

Dla XM określamy: X* = U{Xn | n0}



Czasem wygodnie będzie użyć operacji „plus”: X+ = X*{1}. Zauważmy, że jeśli M jest monoidem, to M*=M, więc M+=M*{1}=M{1} to po prostu zbiór wszystkich elementów M różnych od jedynki.

2.2 MONOID WOLNY

Monoidem wolnym generowanym przez (dowolny) zbiór A nazywamy monoid (A*,), którego elementami (tzn. elementami A*) są wszystkie skończone ciągi elementów zbioru A, jedynką jest ciąg 0-elementowy =(), zwany ciągiem pustym, a operacja złożenia jest określona następująco: jeśli x=(x1,x2,...,xn), y=(y1,y2,...,ym) (n,m0), to xy=(x1,x2,...,xn,y1,y2,...,ym). Nawiasy, przecinki i znak operacji złożenia będą zawsze pomijane, tak więc powyższe ciągi x, y i xy będą zapisywane jako x=x1x2...xn, y=y1y2...ym i xy= x1x2...xny1y2...ym, jedynka zaś oznaczana będzie symbolem . Zbiór A nazywamy alfabetem, elementy A* - słowami, a podzbiory A* - językami.

Podstawowe terminy i oznaczenia: Niech A będzie alfabetem. Słowo xA* nazy­wamy: segmentem słowa wA* jeśli (u,vA*) w=uxv; prefiksem (lub segmentem początkowym) – jeśli (vA*) w=xv; suffiksem (lub segmentem końcowym) – jeśli (uA*) w=ux; posłowem słowa w – jeśli istnieje rozkład w=v0u1v1...unvn taki, że u1...un=x. Długość słowa w, oznaczana przez |w|, to liczba wystąpień liter w słowie w (formalnie: |w|=n wtw wAn); przez |w|a oznaczać będziemy liczbę wystąpień litery a w slowie w.

Teoria języków formalnych (zwana też lingwistyką matematyczną) to teoria pod­zbiorów (czyli języków) monoidów wolnych nad alfabetem skończonym.

2.3 ZBIORY GENERATORÓW

Definicja: Podzbiór PM nazywamy podmonoidem monoidu M wtw 1P  P2P (czyli P jest zamknięty względem złożenia). Jeśli XM, to zbiór X* jest podmonoidem monoidu M; jest to najmniejszy podmonoid M zawierający X.

Definicja: Podzbiór GM nazywamy zbiorem generatorów monoidu M wtw G*=M.

Uwaga: Zbiorem generatorów monoidu wolnego A* jest alfabet A. Jest to najmniejszy zbiór generatorów monoidu A*.

Twierdzenie: Każdy monoid M posiada zbiór generatorów. Każdy podmonoid M monoidu wolnego posiada najmniejszy (zawarty w każdym innym) zbiór generatorów. Jest nim zbiór G=M+(M+)2 elementów nierozkładalnych podmonoidu M.

Dowód: Pierwsze zdanie jest oczywiste, gdyż M*=M, więc cały monoid jest swoim generatorem. Drugą część pokazujemy w dwóch etapach. Najpierw, że G jest zbiorem generatorów M (tu istotnie wykorzystujemy fakt, że jest to podmonoid monoidu wol­nego); potem, że G jest zawarty w każdym zbiorze generatorów (tu już założenie, że M jest podmonoidem wolnego nie jest potrzebne). Szczegóły na ćwiczeniach. 

Twierdzenie: Jeżeli GM jest zbiorem generatorów monoidu M, to M jest obrazem homomorficznym monoidu wolnego nad alfabetem równolicznym z G.

Dowód: Weźmy dowolny zbiór A równoliczny z G i bijekcję f:AG. Naturalne rozszerzenie homomorficzne f:A*G*=M jest szukanym homomorfizmem. 

Wniosek: Każdy monoid jest obrazem homomorficznym jakiegoś monoidu wolnego.

2.4 MORFIZMY, KONGRUENCJE I MONOIDY ILORAZOWE

Definicja: Niech M, M będą monoidami. Funkcja f:MM jest morfizmem wtw

(x,yM) f(xy) = f(x)f(y) oraz f(1M) = 1M



Proste fakty: (1) Jeśli f:MM jest morfizmem, to f(M) jest podmonoidem M.
(2) Każdy morfizm f:A*M jest jednoznacznie wyznaczony przez wartości na literach aA. Ogólniej: Każdy morfizm f:MM jest jednoznacznie wyznaczony przez wartości na dowolnym zbiorze generatorów monoidu M.

Przykłady morfizmów f:A*B*

  • alfabetyczny f(A)  B{}

  • ściśle alfabetyczny f(A)  B

  • -wolny f(A)  B+

  • rzut na XA f(x) = if xX then x else

Definicja: Niech M będzie monoidem. Relację równoważności MM nazywamy kongruencją wtw jest ona zgodna z operacją złożenia, czyli

(x,y,x,yM) xy  xy  xxyy.

Niech M będzie monoidem i niech MM będzie równoważnością w M. Dla każdego xM klasą równoważności elementu x (modulo ) nazywamy zbiór [x]={yM | xy} wszystkich elementów M równoważnych x. Jeśli  jest kongruencją, to w zbiorze M/ wszystkich takich klas możemy określić operację złożenia jako [x][y] = [xy]. Monoid (M/,) wszystkich klas kongruencji  z tak określonym złożeniem nazywamy wtedy monoidem ilorazowym M przez , a funkcję przypisującą każdemu xM jego klasę [x]M/ morfizmem kanonicznym z M na M/.

Odwrotnie, jeśli f:MM jest morfizmem, to relacja MM określona jako:

xy wtw f(x)=f(y)

jest kongruencją wyznaczoną przez morfizm f. Indeksem relacji równoważności  nazywamy liczbę jej klas równoważności. Indeks może być dodatnią liczbą całkowitą lub być nieskończony. Czasem będziemy mówić „indeks morfizmu f”, mając na myśli indeks kongruencji wyznaczonej przez f.

Niech M będzie monoidem, a MM relacją binarną. Kongruencją generowaną przez  nazywamy najmniejszą kongruencję zawierającą . Taka kongruencja istnieje dla dowolnej relacji MM. Budujemy ją w następujący sposób:

Określamy relację MM:

xy wtw (u,v,p,qM) x=upv  y=uqv  (pq  qp)

Zwrotne i przechodnie domknięcie relacji , oznaczane jako *, jest właśnie szukaną kongruencją generowaną przez relację .



Umowa: Zapis M/, gdzie M jest monoidem, a  dowolną relacją binarną w M, oznaczać będzie zawsze monoid ilorazowy M/*, gdzie * jest opisaną wyżej kongruencją generowaną przez .

2.5 PRZEDSTAWIENIA RÓWNANIOWE

Niech A będzie alfabetem skończonym i niech E={u1v1, ..., unvn} będzie skończoną relacją w A* (tzn. ui,viA* dla i=1,...,n). Relację E zapisujemy zwykle jako układ równań E={u1=v1, ..., un=vn}, a parę A;E nazywamy przedstawieniem równaniowym monoidu ilorazowego A*/ (zob. Umowa). Alfabet A i zbiór E będziemy przeważnie wypisywać w postaci jawnej, np. przedstawienie równaniowe A;E, gdzie A={a,b}, a E={ab=aa, ba=aba} będziemy zapisywać jako a,b;ab=aa,ba=aba. Zauważmy, że monoid A; jest izomorficzny z monoidem wolnym A*.



Kilka przykładów (do wykorzystania w najbliższej przyszłości):

Dwa proste monoidy sladów:



  1. a,b ; ab=ba - najprostszy monoid przemienny

  2. a,b,c ; ab=ba, bc=cb - tylko a i c zależne

I kilka innych monoidów:

  1. a,b ; ab=aabb - rozmnażanie par

  2. a,b ; ab= - monoid dwucykliczny

  3. a,b,c,d ; d=adbdc - wyrażenia arytmetyczne z nawiasami

  4. a,b ; b=bba - notacja beznawiasowa

  5. a,b ; ab=ba= = (Z,+) – zadanie do domu

2.6 MONOIDY ŚLADÓW

Monoidem śladów nazywamy każdy monoid zadany przedstawieniem równaniowym A;E, gdzie A jest alfabetem skończonym, a E jest zbiorem równań postaci ab=ba (gdzie a,bA). Monoidy tego typu po raz pierwszy pojawiły się w literaturze, jako narzędzie do badania przekształceń słów (Cartier & Foata, 1969), pod nazwą monoidy wolne częściowo przemienne (free partially commutative monoids). Osiem lat później (Mazurkiewicz 1977) zostały zaproponowane, jako matematyczne narzędzie do badania i opisu działania systemów współbieżnych, pod dziś używaną nazwą monoidy śladów (trace monoids). Zauważmy, że monoid wolny jest szczególnym przypadkiem monoidu śladów, gdyż A*=A,.

Związki monoidów śladów ze współbieżnością będą dokładniej omówione na jednej z późniejszych lekcji. Wcześniej, badając własności algebraiczne i lingwistyczne dowol­nych monoidów, wykorzystamy kilka prostych monoidów śladów jako przykłady.



©operacji.org 2017
wyślij wiadomość

    Strona główna