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

From Studia Informatyczne

Ćwiczenia 1

Ćwiczenie 1

Pokaż, że jeśli w zbiorze \mathds{Z} określimy działanie

x \star  y = x+y-xy,
to (\mathds{Z}, \star) jest monoidem. Sprawdź, czy jest to monoid przemienny.

Rozwiązanie

Najpierw sprawdźmy łączność działania: niech x, y, z  \in \mathds{Z}. Pokażemy, że (x \star y) \star z = x \star (y \star z). Obliczamy: (x \star y) \star z = (x+y-xy)+z-(x+y-xy)z = x+y+z-xy-xz-yz+xyz x \star (y \star z) = x + (y+z-yz) - x(y+z-yz) = x+y+z-xy-xz-yz+xyz.

Zatem działanie jest łączne. Aby pokazać, że struktura jest monoidem, musimy wskazać element neutralny. Pokażemy, że jest nim 0. Istotnie:
\forall x \in \mathds{Z}\ x \star 0 = 0 \star x = 0 + x - 0 \cdot x = x.
Monoid jest przemienny, gdyż x \star y = x+y-xy=y+x-yx = y \star x.

Ćwiczenie 2

Udowodnij, że w monoidzie istnieje dokładnie jeden element neutralny.

Rozwiązanie

Nie wprost. Rozważmy monoid (M, \cdot) i załóżmy, że istnieją co najmniej dwa elementy neutralne e oraz e'. Ponieważ e jest elementem neutralnym, zatem \forall x \in M\ e \cdot x = x; w szczególności dla x=e' mamy e \cdot e' = e'. Z drugiej strony, e' jest elementem neutralnym, zatem \forall x \in M\ x \cdot e' = x; w szczególności dla x=e mamy e \cdot e' = e. Łącząc te dwa wyniki, otrzymujemy e' = e \cdot e' = e, czyli e=e'. Zatem jeśli istniałyby dwa elementy neutralne e i e', to musiałyby być sobie równe, a więc byłyby tym samym elementem.

Dla zainteresowanych

Ćwiczenie 3

Znajdź wszystkie podpółgrupy (podmonoidy) następujących półgrup (monoidów):

(1) (\mathds{Z}_{mod\ 6}, +),
(2) (\mathds{Z}_{mod\ 7}, +),
(3) (\mathds{Z}_{mod\ 4}, \cdot),
(4) (\{0, 1\}, \vee).

Rozwiązanie punktu 1

.(\mathds{Z}_{mod\ 6}, +) jest monoidem. Jego podmonoidy mogą wyglądać następująco:

(1) \{0\} (generowany przez zbiór \{0\}),
(2) \{0, 2, 4\} (generowany przez zbiór \{2\}),
(3) \{0, 3\} (generowany przez zbiór \{3\}),
(4) \{0,1,2,3,4,5\} (generowany przez zbiór \{1\}).

Ćwiczenie 4

Niech f: S \rightarrow T będzie homomorfizmem półgrup. Pokaż, że \mbox{Ker}_f jest kongruencją.

Rozwiązanie

Niech f: S \rightarrow T będzie homomorfizmem półgrupy S w półgrupę T. Mamy pokazać, że
\forall x, y, z \in  S\ x \mbox{Ker}_f y \Rightarrow zx \mbox{Ker}_f zy \wedge xz  \mbox{Ker}_f yz.

Weźmy więc dowolne x, y, z \in S i załóżmy, że x \mbox{Ker}_f y. Z definicji \mbox{Ker}_f mamy, że {f(x)=f(y)}, zatem zachodzą także równości f(x)f(z)=f(y)f(z) oraz f(z)f(x)=f(z)f(y). Ponieważ {f} jest homomorfizmem mamy f(x)f(z)=f(xz), f(y)f(z)=f(yz), f(z)f(x)=f(zx), f(z)f(y)=f(zy). Zatem zachodzą równości f(xz)=f(yz) oraz f(zx)=f(zy), ale to oznacza, że xz \mbox{Ker}_f yz oraz zx \mbox{Ker}_f zy, a to mieliśmy pokazać.

Ćwiczenie 5

Skonstruuj odwzorowanie h: \mathds{Z}_{mod\ 4} \rightarrow  \mathds{Z}_{mod\ 2} tak, aby było homomorfizmem monoidu (\mathds{Z}_{mod\ 4}, \cdot, 1) w monoid (\mathds{Z}_{mod\ 2}, \cdot, 1).

Rozwiązanie

Połóżmy h(0)=h(2)=0, h(1)=h(3)=1. Sprawdź, że h jest homomorfizmem oraz zauważ, że obrazem elementu neutralnego monoidu \mathds{Z}_{mod\ 4} przez homomorfizm h jest element neutralny monoidu \mathds{Z}_{mod\ 2}.

Ćwiczenie 6

Niech (M,\cdot,1_{M}) i (M',*,1_{M'}) będą monoidami, a
h:M \longmapsto M'
suriekcją. Udowodnij, że

h jest homomorfizmem monoidu (M,\cdot,1_{M}) na (M',*,1_{M'}) wtw gdy
\forall x,y \in S \;\;\; h(x\cdot y)=h(x)*h(y). ( Z faktów, że h jest homomorfizmem półgrup i suriekcją należy wywnioskować, że h(1_M) jest elementem neutralnym w M').

Rozwiązanie

\forall m' \in M' \;\exists m \in M :m'=h(m)
m'h(1_M)=h(m)h(1_M)=h(m1_M)=h(m) oraz
h(1_M)m'=h(1_M)h(m)=h(1_Mm)=h(m).

Ćwiczenie 7

Niech (S,\cdot) będzie dowolną półgrupą, a T \subset S dowolnym podzbiorem S. Udowodnij, że relacja {\rho^r_T} \subset S^2 taka, że \forall x,y \in S

x  {\rho^r_T} y \Longleftrightarrow (\forall z \in S\; xz \in T  \Longleftrightarrow yz \in T)
jest prawą kongruencją,

Rozwiązanie

Dowodzimy, że {\rho^r_T} jest relacją równoważności.
\forall  x,y,w \in S

zwrotność:
x\rho^r_T x \Leftrightarrow (\forall z \in S\; xz \in T \Longleftrightarrow xz \in T)


symetria:
x\rho^r_T y \Leftrightarrow (\forall z \in S\; xz \in T \Longleftrightarrow yz \in T) \Leftrightarrow\\ \Leftrightarrow (\forall z \in S\; yz \in T \Longleftrightarrow xz \in T)  \Leftrightarrow y\rho^r_T x \Leftrightarrow


przechodniość:
x\rho^r_T y ,  y\rho^r_T w \Leftrightarrow (\forall z \in S\; xz \in T \Longleftrightarrow yz \in T), (\forall z \in S\; yz \in T \Longleftrightarrow ywz \in T)\Leftrightarrow  (\forall z \in S\; xz \in T \Longleftrightarrow wz \in T) \Leftrightarrow  x\rho^r_T w

Dowodzimy, że {\rho^r_T} jest prawą kongruencją.
\forall x,y \in S
x\rho^r_T y \Rightarrow (\forall z,w \in S\; xzw \in T  \Longleftrightarrow yzw \in T) \Leftrightarrow (\forall z \in S\; xz\rho^r_T yz  ).

Dla zainteresowanych

Ćwiczenie 8

Określ minimalny zbiór generatorów monoidów:

(1) (\mathds{Z}, +, 0),
(2) (\mathds{Z}, \cdot, 1),
(3) (\mathds{Z}_{mod\ 5}, \cdot, 1),
(4) (\mathds{Z}_{mod\ 4}, +, 0).

Rozwiązanie punktu 1

Najmniejszym zbiorem generatorów jest zbiór \{-1, 1\}, choć nie jest to jedyny możliwy taki zbiór generatorów: warunek ten spełnia również na przykład zbiór \{-2, 3\}. Aby to pokazać, wystarczy dowieść, że da się z niego wygenerować elementy 1 oraz -1 i skorzystać z tego, że \{-1, 1\} jest zbiorem generatorów. Mamy 1 = (-2)+3 oraz -1 = (-2)+(-2)+3.


Ćwiczenie 9

Dana jest półgrupa \{a,b\}^+ oraz jej podpółgrupa generowana przez dwuelementowy zbiór słów \{a, ba\}. Opisz słownie elementy tej podpółgrupy.

Rozwiązanie

Jest to zbiór wszystkich (i tylko takich) słów, które nie kończą się literą {b} oraz w których nie występuje podsłowo bb.


Ćwiczenie 10

W monoidzie wolnym \{a, b\}^* rozważamy następujące podmonoidy:

(1) M_1=\{ab, ba, a\}^*,
(2) M_2=\{aa, ba\}^*.

Które z tych monoidów są wolne? W rozwiązaniu wykorzystaj twierdzenie 2.3 z wykładu 1 (patrz twierdzenie 2.3.)

Rozwiązanie punktu 1

Niech S=M_1 \backslash \{1\}. Po pierwsze, zauważmy, że \{ab,ba,a\} \subset S \backslash S^2. Weźmy element aba \in S. Ma on dwa rozkłady na elementy zbioru S \backslash S^2, mianowicie: aba=a \cdot ba = ab \cdot a, zatem monoid M_1 nie jest wolny.

ZADANIA DOMOWE


Rysunek 1

Ćwiczenie 11

Sprawdź, które z poniższych struktur są półgrupami, które monoidami, a które ani półgrupami, ani monoidami. W przypadku monoidów wskaż element neutralny.

(1) (\mathds{Z}, +),
(2) (\mathds{Z}, \cdot),
(3) (\mathds{R}, +),
(4) (\mathds{R}, \cdot),
(5) (\mathds{Z}_{mod\;5}, +),
(6) (\mathds{Z}_{mod\;6}, \cdot),
(7) (\{0, 1\}, \vee),
(8) (\{0, 1\}, \wedge),
(9) (M_n(\mathds{R}), +), gdzie M_n(\mathds{R}) jest rodziną macierzy o wymiarze n \times n o elementach rzeczywistych,
(10) (M_n(\mathds{R}), \cdot), gdzie M_n(\mathds{R}) jest zdefiniowane jak powyżej,
(11) (n\mathds{Z}, +), gdzie n\mathds{Z}=\{mn:\ m \in \mathds{Z}\} jest zbiorem liczb całkowitych podzielnych przez n \in \mathds{N},
(12) zbiór B wszystkich drzew binarnych wraz z działaniem +, zdefiniowanym w sposób przedstawiony na rysunku 1 (czyli działanie na drzewach T_1 i T_2 polega na dodaniu jednego wierzchołka, który jest nowym korzeniem, a jego lewym i prawym dzieckiem są odpowiednio drzewa T_1 i T_2).

Ćwiczenie 12

Które z półgrup i monoidów z zadania 1.11 są przemienne?

Ćwiczenie 13

Niech (S, \circ_S) i (T, \circ_T) będą półgrupami. Sprawdź, czy półgrupami są także:

(1) (S \times T, \circ), gdzie (s_1, t_1) \circ (s_2, t_2) = (s_1 \circ_S s_2, t_1 \circ_T  t_2),
(2) (S \times S, \circ), gdzie \circ=\circ_S i (s_1, s_2) \circ  (s_3, s_4) = (s_1 \circ s_4, s_2 \circ s_3).

Ćwiczenie 14

Podaj przykłady:

(1) jednoelementowego monoidu,
(2) jednoelementowej półgrupy,
(3) monoidów o 3, 5 i 11 elementach,
(4) nieskończonej przeliczalnej półgrupy,
(5) nieskończonej nieprzeliczalnej półgrupy.

Ćwiczenie 15

Podaj przykład półgrupy S i kongruencji \rho taki, że |S|=\infty ale S \slash \rho jest skończona.

Ćwiczenie 16

Rozważmy monoid S=(\mathds{Z}, +) i ustalmy k \in \mathds{N}. Znajdź monoidy ilorazowe S \slash \rho, gdzie relacja \rho zdefiniowana jest następująco (najpierw sprawdź, czy \rho jest kongruencją!):

x \rho y wtw x = y \mod k.

Ćwiczenie 17

Niech (S,\cdot) będzie dowolną półgrupą, a T \subset S dowolnym podzbiorem {S}. Udowodnij, że:

(1) relacja {\rho^l_T} \subset S^2 taka, że \forall x,y \in S
x  {\rho^l_T} y \Longleftrightarrow (\forall z \in S\; zx \in T  \Longleftrightarrow zy \in T)
jest lewą kongruencją,
(2) relacja \rho_T \subset S^2 taka, że \forall x,y \in S
x  \rho_T y \Longleftrightarrow (\forall z_1,z_2 \in S\; z_1xz_2 \in T  \Longleftrightarrow z_1yz_2 \in T)
jest kongruencją.
Dla zainteresowanych

Ćwiczenie 18

W monoidzie wolnym \{a, b\}^* rozważamy następujące podmonoidy:

(1) M_3=\{a, bb, ab\}^*,
(2) M_4=\{ab^2, ab^2a, aba, ba\}^*.
Które z tych monoidów są wolne? W rozwiązaniu wykorzystaj twierdzenie 2.3 z wykładu 1 (patrz twierdzenie 2.3.)