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

Ćwiczenia 1

Ćwiczenie 1

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

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

Rozwiązanie

Najpierw sprawdźmy łączność działania: niech $x,y,z\in \mathbb{\mathbb{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: $\mathrm{\forall }x\in \mathbb{\mathbb{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^{\prime }$. Ponieważ $e$ jest elementem neutralnym, zatem $\mathrm{\forall }x\in Me\cdot x=x$; w szczególności dla $x=e^{\prime }$ mamy $e\cdot e^{\prime }=e^{\prime }$. Z drugiej strony, $e^{\prime }$ jest elementem neutralnym, zatem $\mathrm{\forall }x\in Mx\cdot e^{\prime }=x$; w szczególności dla $x=e$ mamy $e\cdot e^{\prime }=e$. Łącząc te dwa wyniki, otrzymujemy $e^{\prime }=e\cdot e^{\prime }=e$, czyli $e=e^{\prime }$. Zatem jeśli istniałyby dwa elementy neutralne $e$ i $e^{\prime }$, 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) $({\mathbb{\mathbb{Z}}}_{mod6},+)$,

(2) $({\mathbb{\mathbb{Z}}}_{mod7},+)$,

(3) $({\mathbb{\mathbb{Z}}}_{mod4},\cdot )$,

(4) $(\{0,1\},\vee )$.

Rozwiązanie punktu 1

.$({\mathbb{\mathbb{Z}}}_{mod6},+)$ 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\to T$ będzie homomorfizmem półgrup. Pokaż, że ${\text{Ker}}_f$ jest kongruencją.

Rozwiązanie

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

Weźmy więc dowolne $x,y,z\in S$ i załóżmy, że $x{\text{Ker}}_{f}y$. Z definicji ${\text{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{\text{Ker}}_{f}yz$ oraz $zx{\text{Ker}}_{f}zy$, a to mieliśmy pokazać.

Ćwiczenie 5

Skonstruuj odwzorowanie $h:{\mathbb{\mathbb{Z}}}_{mod4}\to {\mathbb{\mathbb{Z}}}_{mod2}$ tak, aby było homomorfizmem monoidu $({\mathbb{\mathbb{Z}}}_{mod4},\cdot ,1)$ w monoid $({\mathbb{\mathbb{Z}}}_{mod2},\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 ${\mathbb{\mathbb{Z}}}_{mod4}$ przez homomorfizm $h$ jest element neutralny monoidu ${\mathbb{\mathbb{Z}}}_{mod2}$.

Ćwiczenie 6

Niech $(M,\cdot ,1_M)$ i $(M^{\prime },*,1_{M^{\prime }})$ będą monoidami, a $h:M⟼M^{\prime }$ suriekcją. Udowodnij, że

$h$ jest homomorfizmem monoidu $(M,\cdot ,1_M)$ na $(M^{\prime },*,1_{M^{\prime }})$ wtw gdy
$\mathrm{\forall }x,y\in Sh(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^{\prime }$).

Rozwiązanie

$\mathrm{\forall }{m}^{\prime }\in M^{\prime }\mathrm{\exists }m\in M:m^{\prime }=h(m)$
$m^{\prime }h(1_M)=h(m)h(1_M)=h(m{1}_M)=h(m)$ oraz
$h(1_M)m^{\prime }=h(1_M)h(m)=h(1_{M}m)=h(m)$.

Ćwiczenie 7

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

$x{\rho }_T^{r}y⟺(\mathrm{\forall }z\in Sxz\in T⟺yz\in T)$ jest prawą kongruencją,

Rozwiązanie

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

zwrotność:
$x{\rho }_T^{r}x\iff (\mathrm{\forall }z\in Sxz\in T⟺xz\in T)$

symetria:
$\begin{array}{r}x{\rho }_T^{r}y\iff (\mathrm{\forall }z\in Sxz\in T⟺yz\in T)\iff \\ \iff (\mathrm{\forall }z\in Syz\in T⟺xz\in T)\iff y{\rho }_T^{r}x\iff \end{array}$

przechodniość:
$x{\rho }_T^{r}y,y{\rho }_T^{r}w\iff (\mathrm{\forall }z\in Sxz\in T⟺yz\in T),(\mathrm{\forall }z\in Syz\in T⟺ywz\in T)$$\iff (\mathrm{\forall }z\in Sxz\in T⟺wz\in T)\iff x{\rho }_T^{r}w$

Dowodzimy, że ${\rho }_T^r$ jest prawą kongruencją.
$\mathrm{\forall }x,y\in S$
$x{\rho }_T^{r}y\Rightarrow (\mathrm{\forall }z,w\in Sxzw\in T⟺yzw\in T)\iff (\mathrm{\forall }z\in Sxz{\rho }_T^{r}yz)$.

Dla zainteresowanych

Ćwiczenie 8

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

(1) $(\mathbb{\mathbb{Z}},+,0)$,

(2) $(\mathbb{\mathbb{Z}},\cdot ,1)$,

(3) $({\mathbb{\mathbb{Z}}}_{mod5},\cdot ,1)$,

(4) $({\mathbb{\mathbb{Z}}}_{mod4},+,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\mathrm{\setminus }\{1\}$. Po pierwsze, zauważmy, że $\{ab,ba,a\}\subset S\mathrm{\setminus }{S}^2$. Weźmy element $aba\in S$. Ma on dwa rozkłady na elementy zbioru $S\mathrm{\setminus }{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) $(\mathbb{\mathbb{Z}},+)$,

(2) $(\mathbb{\mathbb{Z}},\cdot )$,

(3) $(\mathbb{ℝ},+)$,

(4) $(\mathbb{ℝ},\cdot )$,

(5) $({\mathbb{\mathbb{Z}}}_{mod5},+)$,

(6) $({\mathbb{\mathbb{Z}}}_{mod6},\cdot )$,

(7) $(\{0,1\},\vee )$,

(8) $(\{0,1\},\wedge )$,

(9) $(M_n(\mathbb{ℝ}),+)$, gdzie $M_n(\mathbb{ℝ})$ jest rodziną macierzy o wymiarze $n\times n$ o elementach rzeczywistych,

(10) $(M_n(\mathbb{ℝ}),\cdot )$, gdzie $M_n(\mathbb{ℝ})$ jest zdefiniowane jak powyżej,

(11) $(n\mathbb{\mathbb{Z}},+)$, gdzie $n\mathbb{\mathbb{Z}}=\{mn:m\in \mathbb{\mathbb{Z}}\}$ jest zbiorem liczb całkowitych podzielnych przez $n\in \mathbb{\mathbb{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|=\mathrm{\infty }$ ale $S/\rho$ jest skończona.

Ćwiczenie 16

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

$x\rho y$ wtw $x=ymodk$.

Ćwiczenie 17

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

(1) relacja ${\rho }_T^l\subset S^2$ taka, że $\mathrm{\forall }x,y\in S$ $x{\rho }_T^{l}y⟺(\mathrm{\forall }z\in Szx\in T⟺zy\in T)$ jest lewą kongruencją,

(2) relacja ${\rho }_T\subset S^2$ taka, że $\mathrm{\forall }x,y\in S$ $x{\rho }_{T}y⟺(\mathrm{\forall }{z}_1,z_2\in S{z}_{1}x{z}_2\in T⟺z_{1}y{z}_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=\{a{b}^2,a{b}^{2}a,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.)