Języki, automaty i obliczenia/Wykład 1: Słowa, katenacja - elementy teorii półgrup, półgrupy i monoidy wolne

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Definicje, oznaczenia i podstawowe własności

Przyjmijmy, że oznacza zbiór liczb naturalnych, a zbiór liczb naturalnych wraz z 0. Przypomnimy teraz podstawowe wiadomości z wykładu Algebra Liniowa dotyczące struktur algebraicznych, a dokładniej struktur najprostszych, półgrup i monoidów, posiadających jedno tylko działanie.

Definicja 1.1

Zbiór , w którym określone jest działanie łączne, to znaczy spełniające warunek

nazywamy półgrupą.

Przykład 1.1

Zbiór liczb naturalnych z dodawaniem tworzy półgrupę.

Definicja 1.2

Półgrupę , w której istnieje element neutralny działania, to znaczy element spełniający warunek

nazywamy monoidem.

Przykład 1.2

(1) Zbiór liczb naturalnych z mnożeniem jest monoidem.
(2) Zbiór liczb naturalnych z zerem jest monoidem ze względu na dodawanie.
(3) Monoidem jest - zbiór odwzorowań dowolnego zbioru w siebie ze składaniem jako działaniem i identycznością jako elementem neutralnym.

Dwa pierwsze monoidy są przemienne, czyli działanie jest przemienne, a trzeci jest nieprzemienny.

Każdy monoid jest półgrupą.

Dla uproszczenia notacji będziemy opuszczać kropkę "" oznaczającą działanie oraz używać nazwy "jedynka" na element neutralny. Jeśli nie będzie zaznaczone inaczej, to będzie oznaczać półgrupę, a monoid. Ze względu na łączność działania zarówno w półgrupie, jak i w monoidzie iloczyn a także (n razy) jest określony jednoznacznie bez potrzeby wprowadzania nawiasów. Dla dowolnych liczb naturalnych zachodzą wzory

Dla dowolnego przyjmujemy z definicji

Strukturę monoidu przenosimy na zbiór potęgowy wszystkich podzbiorów monoidu , określając dla dowolnych działanie

jest monoidem.
Podobnie przenosimy strukturę półgrupy z na .
Dla dowolnego podzbioru monoidu (półgrupy) i dla dowolnej liczby zapis oznacza n-krotny iloczyn zbioru przez siebie rozumiany w powyższym sensie.
W szczególności

W przypadku monoidu przyjmujemy z definicji

Definicja 1.3

Homomorfizmem półgrup nazywamy odwzorowanie

takie, że

Homomorfizmem monoidów nazywamy odwzorowanie

takie, że

Przykład 1.3

Odwzorowanie takie, że

jest homomorfizmem półgrupy w półgrupę , ale nie jest homomorfizmem monoidu w monoid , bo wartością 1 z monoidu nie jest jedynka monoidu .

Dla zainteresowanych

Definicja 1.4.

Niech będą odpowiednio dowolną półgrupą, monoidem.

  • nazywamy podpółgrupą wtedy i tylko wtedy, gdy i
  • nazywamy podmonoidem wtedy i tylko wtedy, gdy jest podpółgrupą i

Przykład 1.4.

jest monoidem. Podzbiór , jako zamknięty na działanie , tworzy podpółgrupę . jest monoidem z jako elementem neutralnym, ale nie podmonoidem .

Niech będzie dowolnym podzbiorem monoidu . Zbiór



jest podmonoidem monoidu . Jest to najmniejszy, w sensie inkluzji podmonoid monoidu zawierający zbiór . Gdy spełniona jest równość , to mówimy, że jest zbiorem generatorów monoidu . Zachodzą następujące własności:

1. Zbiór generatorów nie jest wyznaczony jednoznacznie.
2. Dla dowolnego monoidu istnieje zbiór generatorów, jest nim w szczególności zbiór .

Podobnie dla dowolnego podzbioru półgrupy zbiór



jest podpółgrupą i to najmniejszą w sensie inkluzji zawierającą zbiór .
Powyższe uwagi dotyczące zbioru generatorów monoidów przenoszą się odpowiednio dla półgrup.

Przykład 1.5.

W monoidzie podmonoid generowany przez zbiór generatorów składa się z liczb parzystych i nieujemnych.

Definicja 1.5

Niech będzie półgrupą. Relację równoważności nazywamy:

(1) prawą kongruencją w półgrupie , jeśli
(2) lewą kongruencją w półgrupie , jeśli
(3) kongruencją, jeśli jest prawą i lewą kongruencją, tzn.

Zastępując w powyższej definicji półgrupę na monoid otrzymamy dualnie pojęcia prawej kongruencji, lewej kongruencji i kongruencji zdefiniowane w monoidzie.
Mając kongruencję określoną w półgrupie (monoidzie możemy utworzyć półgrupę ilorazową (monoid ilorazowy ), której elementami są klasy równoważności (abstrakcji) relacji .

Dla dowolnego homomorfizmu półgrup określamy relację

Relacja jest kongruencją w półgrupie

Dla homomorfizmu monoidów relacja jest kongruencją w monoidzie .

Podstawowe twierdzenie o epimorfizmie dla struktur algebraicznych przyjmuje dla półgrup i odpowiednio dla monoidów następującą postać.

Twierdzenie 1.1

Niech będzie dowolnym epimorfizmem półgrupy na półgrupę Półgrupa jest izomorficzna z półgrupą ilorazową .

<flash>file=Ja-1-1.swf|width=200|height=200</flash> <div.thumbcaption>Rysunek 1

Twierdzenie 1.2

Niech będzie dowolnym epimorfizmem monoidu na monoid Monoid jest izomorficzny z monoidem ilorazowym .

Rysunek 2

Półgrupy wolne i monoidy wolne

Niech oznacza dowolny zbiór.

Definicja 2.1

Wolnym monoidem o bazie nazywamy zbiór wszystkich skończonych ciągów:

wraz z działaniem

Ciąg pusty oznaczamy symbolem "1" i z definicji jest on elementem neutralnym określonego powyżej działania, nazywanego katenacją lub konkatenacją.

Przyjmujemy następującą konwencję zapisu:
W oparciu o nią możemy stwierdzić inkluzję .
Dla zainteresowanych

Ta inkluzja uzasadnia użycie wprowadzonego wcześniej oznaczenia .
jest najmniejszym podmonoidem monoidu zawierającym

Definicja 2.2

Wolną półgrupą nad alfabetem nazywamy zbiór wszystkich skończonych ciągów:

wraz z działaniem katenacji.

Używa się także określeń - wolny monoid o bazie i wolna półgrupa o bazie .

  • Elementy alfabetu nazywamy literami.
  • Elementy wolnego monoidu (półgrupy) nazywamy słowami i oznaczać bedziemy w wykładzie najczęściej literami .
  • Dowolny podzbiór wolnego monoidu (półgrupy) nazywamy językiem.

Długością słowa nazywamy liczbę będącą długością ciągu określającego to słowo. Słowo puste 1, czyli odpowiadające ciągowi pustemu ma długość równą 0.

Przykład 2.1

(1) Wolna półgrupa składa się z ciągów binarnych.
(2) Wolny monoid składa się z ciągów binarnych i ciągu pustego.

Definicja 2.3

Niech i będą alfabetami. Podstawieniem nazywamy homomorfizm

Odwzorowanie jako homomorfizm monoidu w monoid spełnia dla dowolnych równość

Dla zainteresowanych

Twierdzenie 2.1.

Niech oznacza dowolny zbiór, a dowolny monoid.

(1) Każde odwzorowanie
daje się jednoznacznie rozszerzyć do homomorfizmu
(2) Homomorfizm jest epimorfizmem wtedy i tylko wtedy, gdy jest zbiorem generatorów


Dowód

(1) Przyjmujemy
Tak określone jest jedynym rozszerzeniem przekształcenia .
(2) dla pewnego jest suriekcją.


Przyjmując w powyższym twierdzeniu jako dowolny zbiór generatorów monoidu oraz jako funkcję włożenie równe identyczności na dochodzimy do następującego wniosku.

Wniosek 2.1.

Każdy monoid jest homomorficznym obrazem wolnego monoidu  utworzonego nad dowolnym zbiorem generatorów

Udowodnione powyżej twierdzenie oraz sformułowany wniosek prawdziwy jest również dla półgrup.
Powyższe rezultaty określają rolę wolnych monoidów (półgrup) w klasie wszystkich monoidów (półgrup).

Twierdzenie 2.2.

Monoid jest wolny wtedy i tylko wtedy, gdy każdy element ma jednoznaczny rozkład na elementy zbioru

Dowod

Załóżmy, że monoid jest wolny, to znaczy dla pewnego zbioru (bazy)

  • Udowodnimy, że jest zbiorem generatorów monoidu . W tym celu wykażemy, że zachodzi inkluzja
    Dowód przeprowadzimy nie wprost. Załóżmy więc, że
i niech oznacza element z tego zbioru o najmniejszej długości w
Wnioskujemy stąd kolejno:



dla pewnych ,

przy czym długość jest silnie mniejsza niż długość Zatem
a to oznacza, że
Otrzymana sprzeczność kończy dowód faktu, że jest zbiorem generatorów monoidu
  • Pokażemy teraz, że
    Niech dla pewnych ,
    Jeśli , to , co jest sprzeczne z wyborem Zatem , co implikuje

Z definicji wolnego monoidu wynika jednoznaczność rozkładu na elementy z bazy , a to pociąga za sobą jednoznaczność rozkładu na elementy z podzbioru

Niech teraz oznacza monoid z jednoznacznością rozkładu na elementy zbioru . Rozszerzamy identyczność do homomorfizmu Z założenia wynika, że każdy element można przedstawić jako iloczyn

Zatem

Homomorfizm jest izomorfizmem, więc monoid jako izomorficzny z jest wolny.

Powyższe twierdzenie posiada swój odpowiednik dla wolnych półgrup.

Twierdzenie 2.3.

Półgrupa jest wolna wtedy i tylko wtedy, gdy każdy element ma jednoznaczny rozkład na elementy zbioru

Wniosek 2.2.

Baza wolnego monoidu (półgrupy) jest minimalym zbiorem generatorów.

Przyklad 2.2.

(1) Półgrupa jest wolna. Każdy jej element można jednoznacznie zapisać jako sumę jedynek - .
(2) Dla półgrupa nie jest to półgrupą wolną.
Nie ma jednoznaczności rozkładu na elementy z .
Na przykład .