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

{theor}{TWIERDZENIE}[section] {rem}{UWAGA}[section] {corol}{WNIOSEK}[section] {fact}{FAKT}[section] {ex}{PRZYK{}AD}[section] {defin}{DEFINICJA}[section] {lem}{LEMAT}[section]

{prf}{DOWÓD}

{Elementy teorii pó{}grup,
pó{}grupy i monoidy wolne}

Wprowadzenie: Teoria języków formalnych, automatów i gramatyk to klasyczna dzisiaj teoria, która

zajmuje istotne miejsce w informatyce. Proponuje ona matematyczne modele obliczeń, które wykorzystywane są w praktyce, na przykład w przetwarzaniu tekstu, projektowaniu kompilatorów, w językach programowania czy też sztucznej inteligencji. Daje też znakomite podstawy dla teorii obliczalności czy teorii złożoności.

Wykład rozpoczniemy od omówienia półgrup - struktur algebraicznych o niezbyt skomplikowanej budowie, bo posiadających jedno tylko działanie. Półgrupy bowiem tworzą ramy dla prezentacji i badań języków formalnych oraz systemów, które takie języki definiują. Wykład zawiera podstawowe pojęcia oraz elementarne własności z zakresu teorii półgrup.

Słowa kluczowe: półgrupa, monoid, kongruencja, zbiór generatorów, wolny monoid, wolna półgrupa,

baza, alfabet, słowo, litera

DEFINICJE OZNACZENIA I PODSTAWOWE WŁASNOŚCI

Przyjmijmy, że $ℕ = {1, 2, \dots}$ oznacza zbiór liczb naturalnych, a $ℕ_{0}$ 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.

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

\forall x, y, z \in S x \cdot (y \cdot z) = (x \cdot y) \cdot z

nazywamy półgrupą.

Ćwiczenie [Uzupelnij]

Zbiór liczb naturalnych z dodawaniem $(ℕ, +)$ tworzy półgrupę.

Półgrupę $M$ , w której istnieje element neutralny działania, to znaczy element $1_{M} \in M$ spełniający warunek

\forall x \in M 1_{M} \cdot x = x \cdot 1_{M} = x

nazywamy monoidem.

Ćwiczenie [Uzupelnij]

Zbiór liczb naturalnych z mnożeniem $(ℕ, \cdot, 1)$ jest monoidem.

Zbiór liczb naturalnych z zerem $(ℕ_{0}, +, 0)$ jest monoidem ze względu na dodawanie.

Monoidem jest $(A^{A}, \circ, i d_{A})$ - zbiór odwzorowań dowolnego zbioru $A$ w siebie ze składaniem jako dzialaniem

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ę " $\cdot$ " oznaczającą działanie oraz używać nazwy "jedynka" na element neutralny. Jeśli nie będzie zaznaczone inaczej, to $(𝐒, \cdot)$ będzie oznaczać półgrupę, a $(𝐌, \cdot, 1_{𝐌})$ monoid. Ze względu na łączność działania zarówno w półgrupie, jak i w monoidzie iloczyn $x_{1} . . . x_{n},$ a także $x^{n} = x . . . x$ (n razy) jest określony jednoznacznie bez potrzeby wprowadzania nawiasów. Dla dowolnych liczb naturalnych $m, n \in ℕ$ zachodzą wzory

\begin{array}{c} x^{m + n} = x^{m} x^{n} = x^{n} x^{m} \\ (x^{m})^{n} = x^{m n} \end{array} .

Dla dowolnego

x \in M

przyjmujemy z definicji

x^{0} = 1_{M} .

Strukturę monoidu $M$ przenosimy na zbiór potęgowy $𝒫 (M)$ wszystkich podzbiorów monoidu $M$ , określając dla dowolnych $A, B \in 𝒫 (M)$ działanie

Parser nie mógł rozpoznać (błąd składni): {\displaystyle A\cdot B=\left\{ x\in {\bf M}\: :\: \exists a\in A,\: \exists b\in B\: ,\: x=ab\right\} }

$(𝒫 (M), \cdot, {1_{M}})$ jest monoidem.
Podobnie przenosimy strukturę półgrupy z $S$ na $𝒫 (S)$ .
Dla dowolnego podzbioru monoidu (półgrupy) i dla dowolnej liczby $n \in ℕ$ zapis $A^{n}$ oznacza n-krotny iloczyn zbioru $A$ przez siebie rozumiany w powyższym sensie.
W szczególności $A^{1} = A .$

W przypadku monoidu przyjmujemy z definicji

A^{0} = {1_{M}} .

Homomorfizmem półgrup $(S, \cdot), (S^{'}, *)$ nazywamy odwzorowanie

h : S ⟼ S^{'}

takie, że

\forall x, y \in S h (x \cdot y) = h (x) * h (y) .

Homomorfizmem monoidów $(M, \cdot, 1_{M}), (M^{'}, *, 1_{M^{'}})$ nazywamy odwzorowanie $h : M ⟼ M^{'}$

takie, że

\forall x, y \in M h (x \cdot y) = h (x) * h (y) i h (1_{M}) = 1_{M^{'}} .

Ćwiczenie [Uzupelnij]

Odwzorowanie $h : ℤ_{m o d 3} ⟶ ℤ_{m o d 6}$ takie, że

\begin{array}{c} \begin{array}{l} 1 ⟶ 4 \\ 0 ⟶ 0 \\ 2 ⟶ 2 \end{array} \end{array}

jest homomorfizmem półgrupy $(ℤ_{m o d 3}, \cdot)$ w półgrupę $(ℤ_{m o d 6}, \cdot)$ , ale nie jest homomorfizmem monoidu $(ℤ_{m o d 3}, \cdot, 1)$ w monoid $(ℤ_{m o d 6}, \cdot, 1)$ , bo wartością $1$ z monoidu $(ℤ_{m o d 3}, \cdot, 1)$ nie jest jedynka monoidu $(ℤ_{m o d 6}, \cdot, 1)$ .

dla dociekliwych - start ------

Niech $(S, \cdot), (M, \cdot, 1_{M})$ będą odpowiednio dowolną półgrupą, monoidem.

$(T, \cdot)$ nazywamy podpółgrupą $S$ wtedy i tylko wtedy, gdy $T \subset S$ i $T^{2} \subset T .$

$(N, \cdot, 1_{M})$ nazywamy podmonoidem $M$ wtedy i tylko wtedy, gdy $N$ jest podpółgrupą $M$ i $1_{M} \in N .$

Ćwiczenie [Uzupelnij]

$(ℤ_{m o d 6}, \cdot)$ jest monoidem. Podzbiór ${2, 4}$ , jako zamknięty na działanie $\cdot_{m o d 6}$ , tworzy podpółgrupę $ℤ_{m o d 6}$ . $({2, 4}, \cdot_{m o d 6})$ jest monoidem z $4$ jako elementem neutralnym, ale nie podmonoidem $ℤ_{m o d 6}$ .

Niech $X$ będzie dowolnym podzbiorem monoidu $M$ . Zbiór

X^{*} = {1} \cup X \cup X^{2} \cup . . . \cup X^{n} \cup \dots = ⋃_{i = 0}^{\infty} X^{i}

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

Zbiór generatorów nie jest wyznaczony jednoznacznie.

Dla dowolnego monoidu istnieje zbiór generatorów, jest nim w szczególności zbiór $M$ .

Podobnie dla dowolnego podzbioru $X$ półgrupy $S$ zbiór

X^{+} = X \cup X^{2} \cup . . . \cup X^{n} \cup \dots = ⋃_{i = 1}^{\infty} X^{i}

jest podpółgrupą

S

i to najmniejszą w sensie

inkluzji zawierającą zbiór $X .$
Powyższe uwagi dotyczące zbioru generatorów monoidów przenoszą się odpowiednio dla półgrup.

Ćwiczenie [Uzupelnij]

W monoidzie $(ℕ_{0}, +, 0)$ podmonoid generowany przez zbiór generatorów $X = {2}$ składa się z liczb parzystych i nieujemnych.

dla dociekliwych - end -----

Niech $S$ będzie półgrupą. Relację równoważności $ρ \subset S^{2}$ nazywamy:

prawą kongruencją w półgrupie $S$ ,

jeśli

\forall x, y, z \in S x ρ y \Rightarrow x z ρ y z,

lewą kongruencją w półgrupie $S$ , jeśli $\forall x, y, z \in S x ρ y \Rightarrow z x ρ z y,$

kongruencją, jeśli jest prawą i lewą

kongruencją, tzn.

\forall x, y, z \in S x ρ y \Rightarrow z x ρ z y i x z ρ y z .

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

Dla dowolnego homomorfizmu półgrup $h : S ⟼ S^{'}$ określamy relację

K e r_{h} = {(x, y) \in S \times S : h (x) = h (y)} .

Relacja

K e r_{h}

jest

kongruencją w półgrupie $S .$
Dla homomorfizmu monoidów $h : M ⟼ M^{'}$ relacja $K e r_{h}$ jest kongruencją w monoidzie $M$ .

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

Niech $h : S ⟼ S^{'}$ będzie dowolnym epimorfizmem półgrupy $S$ na półgrupę $S' .$ Półgrupa $S'$ jest izomorficzna z półgrupą ilorazową $S /_{K e r_{h}}$ .

rys-01

Niech $h : M ⟼ M^{'}$ będzie dowolnym epimorfizmem monoidu $M$ na monoid $M' .$ Monoid $M'$ jest izomorficzny z monoidem ilorazowym $M /_{K e r_{h}}$ .

rys-02

PÓŁGRUPY WOLNE I MONOIDY WOLNE

Niech $A$ oznacza dowolny zbiór.

Wolnym monoidem $A^{*}$ o bazie $A$ nazywamy

zbiór wszystkich skończonych ciągów:

A^{*} = {(a_{1}, . . ., a_{n}) : n \geq 0, a_{i} \in A}

wraz z działaniem

(a_{1}, . . ., a_{n}) \cdot (b_{1}, . . ., b_{m}) = (a_{1}, . . ., a_{n}, b_{1}, . . ., b_{m}) .

Ciąg pusty (n=0) 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:

(a) \equiv a, (a_{1}, . . ., a_{n}) \equiv a_{1} . . . a_{n} .

W oparciu o nią możemy

stwierdzić inkluzję $A \subset A^{*}$ .

dla dociekliwych - start -----

Ta inkluzja uzasadnia użycie wprowadzonego wcześniej (Uzupelnic lab1|) oznaczenia $A^{*}$ .
$A^{*}$ jest najmniejszym podmonoidem monoidu $A^{*}$ zawierającym $A .$

dla dociekliwych - end -----

Wolną półgrupą $A^{+}$ nad alfabetem $A$ nazywamy zbiór wszystkich skończonych ciągów:

A^{+} = {(a_{1}, . . ., a_{n}) : n > 0, a_{i} \in A}

wraz z

działaniem katenacji.

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

elementy alfabetu $A$ nazywamy literami.

Elementy wolnego monoidu (półgrupy) nazywamy słowami i

oznaczać bedziemy w wykładzie najczęściej literami $u, v, w$ .

Dowolny podzbiór wolnego monoidu (półgrupy)

nazywamy językiem.

Długością słowa $w \in A^{*}$ nazywamy liczbę $| w |$ 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$ .

Ćwiczenie [Uzupelnij]

Wolna półgrupa ${0, 1}^{+}$ składa się z ciągów binarnych.

Wolny monoid ${0, 1}^{*}$ składa się z ciągów binarnych i ciągu pustego.

Niech $A$ i $B$ będą alfabetami. Podstawieniem nazywamy homomorfizm

s : A^{*} ⟶ 𝒫 (B^{*}) .

Odwzorowanie $s$ jako homomorfizm monoidu $A^{*}$ w monoid $𝒫 (B^{*})$ spełnia

dla dowolnych

v, w \in A^{*}

równość

s (v w) = s (v) s (w) oraz s (1) = {1}

.

dla dociekliwych - start -----

Niech $A$ oznacza dowolny zbiór, a $(M, \cdot, 1_{M})$ dowolny monoid.

Każde odwzorowanie $f : A ⟼ M$ daje się

jednoznacznie rozszerzyć do homomorfizmu

h : A^{*} ⟼ M .

Homomorfizm $h$ jest epimorfizmem wtedy i tylko wtedy,

gdy $f (A)$ jest zbiorem generatorów $M .$

Przyjmujemy

\forall a_{1} . . . a_{n} \in A^{+} h (a_{1} . . . a_{n}) = f (a_{1}) . . . f (a_{n}) oraz h (1) = 1_{M} .

Tak określone

h

jest jedynym rozszerzeniem przekształcenia

f

.

$f (A)^{*} = M \Leftrightarrow \forall s \in M s = f (a_{1}) . . . f (a_{n}) = h (a_{1} . . . a_{n})$ dla pewnego

Parser nie mógł rozpoznać (nieznana funkcja „\Leftrightarrowh”): {\displaystyle a_1...a_n \in A^*\Leftrightarrowh} jest suriekcją

$♢$

Przyjmując w powyższym twierdzeniu jako $A$ dowolny zbiór generatorów monoidu $M$ oraz jako funkcję $f$ włożenie $i d_{A} : A ⟶ 𝐌$ równe identyczności na $A$ dochodzimy do następującego wniosku.

Każdy monoid $M$ jest homomorficznym obrazem wolnego monoidu $A^{*}$ utworzonego nad dowolnym zbiorem generatorów $M .$

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).

Monoid $M$ jest wolny wtedy i tylko wtedy, gdy każdy element $m \in S = M ∖ {1}$ ma jednoznaczny rozkład na elementy zbioru $A = S ∖ S^{2} .$

Załóżmy, że monoid $M$ jest wolny, to znaczy $M = B^{*}$ dla pewnego zbioru (bazy) $B .$

Udowodnimy, że $A$ jest zbiorem generatorów monoidu $M$ . W tym celu

wykażemy, że zachodzi inkluzja

S \subset (S ∖ S^{2})^{+} .

Dowód przeprowadzimy nie wprost. Załóżmy więc, że

S ∖ (S ∖ S^{2})^{+} \neq \emptyset

i niech

m

oznacza element z tego zbioru o

najmniejszej długości w $B^{*} .$
Wnioskujemy stąd kolejno:

m ({S} {S}^2)^+
m {S}^2
m=s_1s_2 {dla pewnych} s_1,s_2 {S},

przy czym długość $s_{1}, s_{2}$ jest silnie mniejsza niż długość $m .$ Zatem

s_{1}, s_{2} \in (S ∖ S^{2})^{+}

a to oznacza, że

m = s_{1} s_{2} \in (S ∖ S^{2})^{+} .

Otrzymana sprzeczność kończy dowód faktu, że $A = S ∖ S^{2}$ jest zbiorem generatorów monoidu $M .$

Pokażemy teraz, że $A \subset B .$

Niech $m = b_{1} . . . b_{k} \in S ∖ S^{2}$ dla pewnych $b_{i} \in B$ , $i = 1, . . ., k .$
Jeśli $k > 1$ , to $m \in S^{2}$ , co jest sprzeczne z wyborem $m .$ Zatem $k = 1$ , co implikuje $A \subset B .$

Z definicji wolnego monoidu wynika jednoznaczność rozkładu na elementy z bazy $B$ , a to pociąga za sobą jednoznaczność rozkładu na elementy z podzbioru $A = S ∖ S^{2} .$

Niech teraz $M$ oznacza monoid z jednoznacznością rozkładu na elementy zbioru $A = S ∖ S^{2}$ . Rozszerzamy identyczność $i d_{A} : A ⟼ M$ do homomorfizmu $h : A^{*} ⟼ M .$ Z założenia wynika, że każdy

element

m \in S

można przedstawić jako iloczyn

m = a_{1} . . . a_{n} g d z i e a_{i} \in A d l a i = 1, . . ., n .

Zatem

h (a_{1} . . . a_{n}) = h (a_{1}) . . . h (a_{n}) = a_{1} . . . a_{n} .

Homomorfizm

h

jest

izomorfizmem, więc monoid $M$ jako izomorficzny z $A^{*}$ jest wolny.

$♢$

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

Półgrupa $S$ jest wolna wtedy i tylko wtedy, gdy każdy element $x \in S$ ma jednoznaczny rozkład na elementy zbioru $S ∖ S^{2} .$

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

Ćwiczenie [Uzupelnij]

Półgrupa $(ℕ, +)$ jest wolna. Każdy jej element można jednoznacznie zapisać

jako sumę jedynek - $ℕ ∖ (ℕ + ℕ) = {1}$ .

Dla $ℕ_{2} = {n \in ℕ : n \geq 2}$ półgrupa $(ℕ_{2}, +)$ nie jest to półgrupą wolną.

Nie ma jednoznaczności rozkładu na elementy z $ℕ_{2} ∖ (ℕ_{2} + ℕ_{2}) = {2, 3}$ .
Na przykład $6 = 2 + 2 + 2 = 3 + 3$ .

dla dociekliwych - end -----

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

DEFINICJE OZNACZENIA I PODSTAWOWE WŁASNOŚCI

PÓŁGRUPY WOLNE I MONOIDY WOLNE

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia