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

Ćwiczenia 1

Ćwiczenie 1.1

Pokaż, że jeśli w zbiorze Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \mathds{Z}} określimy działanie $x\star y=x+y-xy,$ to Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle (\mathds{Z}, \star)} jest monoidem. Sprawdź, czy jest to monoid przemienny.

Rozwiązanie

Najpierw sprawdźmy łączność działania: niech Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle 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: Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \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 1.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.

Uwaga [dla zainteresowanych ćwiczenie 1.3]

{{{3}}}

Rozwiązanie punktu 1

.Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle (\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 1.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 1.5

Skonstruuj odwzorowanie Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle h: \mathds{Z}_{mod\ 4} \rightarrow \mathds{Z}_{mod\ 2}} tak, aby było homomorfizmem monoidu Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle (\mathds{Z}_{mod\ 4}, \cdot, 1)} w monoid Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle (\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 Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \mathds{Z}_{mod\ 4}} przez homomorfizm $h$ jest element neutralny monoidu Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \mathds{Z}_{mod\ 2}} .

Ćwiczenie 1.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 1.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:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 }_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)$.

Ćwiczenie 1.8

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

(1) Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle (\mathds{Z}, +, 0)} ,

(2) Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle (\mathds{Z}, \cdot, 1)} ,

(3) Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle (\mathds{Z}_{mod\ 5}, \cdot, 1)} ,

(4) Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle (\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 1.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 1.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 $??$ z wykładu ja-lekcja1-w.

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

Ćwiczenie 1.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) Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle (\mathds{Z}, +)} ,

(2) Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle (\mathds{Z}, \cdot)} ,

(3) Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle (\mathds{R}, +)} ,

(4) Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle (\mathds{R}, \cdot)} ,

(5) Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle (\mathds{Z}_{mod\;5}, +)} ,

(6) Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle (\mathds{Z}_{mod\;6}, \cdot)} ,

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

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

(9) Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle (M_n(\mathds{R}), +)} , gdzie Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle M_n(\mathds{R})} jest rodziną macierzy o wymiarze $n\times n$ o elementach rzeczywistych,

(10) Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle (M_n(\mathds{R}), \cdot)} , gdzie Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle M_n(\mathds{R})} jest zdefiniowane jak powyżej,

(11) Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle (n\mathds{Z}, +)} , gdzie Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle n\mathds{Z}=\{mn:\ m \in \mathds{Z}\}} jest zbiorem liczb całkowitych podzielnych przez Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle n \in \mathds{N}} ,

(12) zbiór $B$ wszystkich drzew binarnych wraz z działaniem $+$, zdefiniowanym w następujący sposób:

RYSUNEK NR 1 (plik JA-lekcja1-c-rys1.bmp)

(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 1.12

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

Ćwiczenie 1.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 1.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 1.15]

Podaj przykład półgrupy $S$ i kongruencji $\rho$ taki, że $|S|=\mathrm{\infty }$ ale Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle S \slash \rho} jest skończona.

Ćwiczenie 1.16

Rozważmy monoid Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle S=(\mathds{Z}, +)} i ustalmy Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle k \in \mathds{N}} . Znajdź monoidy ilorazowe Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle S \slash \rho} , gdzie relacja $\rho$ zdefiniowana jest następująco (najpierw sprawdź, czy $\rho$ jest kongruencją!):

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

Ćwiczenie 1.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ą.

Ćwiczenie 1.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 $??$ z wykładu ja-lekcja1-w.