Języki, automaty i obliczenia/Ćwiczenia 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] {cw}{ĆWICZENIE}[section]

{prf}{DOWÓD}

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

Ćwiczenia 1

Ćwiczenie [Uzupelnij]

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 [Uzupelnij]

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.

Ćwiczenie [Uzupelnij]

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

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

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

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

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

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\}$),

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

1. $\{0,3\}$ (generowany przez zbiór $\{3\}$),

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

Ćwiczenie [Uzupelnij]

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 [Uzupelnij]

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 [Uzupelnij]

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 [Uzupelnij]

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 [Uzupelnij]

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

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

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

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

1. 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 [Uzupelnij]

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 [Uzupelnij]

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

1. $M_1=\{ab,ba,a{\}}^{*}$,

1. $M_2=\{aa,ba{\}}^{*}$,

Które z tych monoidów są wolne? W rozwiązaniu wykorzystaj twierdzenie Uzupelnic tw:b| 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 [Uzupelnij]

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}, +)} ,

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

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

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

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

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

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

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

1. 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,

1. 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,

1. 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}} ,

1. 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 [Uzupelnij]

Które z półgrup i monoidów z zadania Uzupelnic zad1| są przemienne?

Ćwiczenie [Uzupelnij]

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)$,

1. $(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 [Uzupelnij]

Podaj przykłady:

1. jednoelementowego monoidu,

1. jednoelementowej półgrupy,

1. monoidów o 3, 5 i 11 elementach,

1. nieskończonej przeliczalnej półgrupy,

1. nieskończonej nieprzeliczalnej półgrupy.

Ćwiczenie [Uzupelnij]

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 [Uzupelnij]

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 [Uzupelnij]

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ą,

1. 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 [Uzupelnij]

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

1. $M_3=\{a,bb,ab{\}}^{*}$,

1. $M_4=\{a{b}^2,a{b}^{2}a,aba,ba{\}}^{*}$.

Które z tych monoidów są wolne? W rozwiązaniu wykorzystaj twierdzenie Uzupelnic tw:b| z wykładu ja-lekcja1-w.