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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ćwiczenia 1

Ćwiczenie 1

Pokaż, że jeśli w zbiorze określimy działanie

to jest monoidem. Sprawdź, czy jest to monoid przemienny.
Rozwiązanie

Ćwiczenie 2

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

Rozwiązanie
Dla zainteresowanych

Ćwiczenie 3

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

(1) ,
(2) ,
(3) ,
(4) .
Rozwiązanie punktu 1

Ćwiczenie 4

Niech będzie homomorfizmem półgrup. Pokaż, że jest kongruencją.

Rozwiązanie

Ćwiczenie 5

Skonstruuj odwzorowanie tak, aby było homomorfizmem monoidu w monoid .

Rozwiązanie

Ćwiczenie 6

Niech i będą monoidami, a
suriekcją. Udowodnij, że

jest homomorfizmem monoidu na wtw gdy
( Z faktów, że jest homomorfizmem półgrup i suriekcją należy wywnioskować, że jest elementem neutralnym w ).

Rozwiązanie

Ćwiczenie 7

Niech będzie dowolną półgrupą, a dowolnym podzbiorem . Udowodnij, że relacja taka, że

jest prawą kongruencją,
Rozwiązanie
Dla zainteresowanych

Ćwiczenie 8

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

(1) ,
(2) ,
(3) ,
(4) .
Rozwiązanie punktu 1


Ćwiczenie 9

Dana jest półgrupa oraz jej podpółgrupa generowana przez dwuelementowy zbiór słów . Opisz słownie elementy tej podpółgrupy.

Rozwiązanie


Ćwiczenie 10

W monoidzie wolnym rozważamy następujące podmonoidy:

(1) ,
(2) .

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
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) ,
(2) ,
(3) ,
(4) ,
(5) ,
(6) ,
(7) ,
(8) ,
(9) , gdzie jest rodziną macierzy o wymiarze o elementach rzeczywistych,
(10) , gdzie jest zdefiniowane jak powyżej,
(11) , gdzie jest zbiorem liczb całkowitych podzielnych przez ,
(12) zbiór wszystkich drzew binarnych wraz z działaniem , zdefiniowanym w sposób przedstawiony na rysunku 1 (czyli działanie na drzewach i polega na dodaniu jednego wierzchołka, który jest nowym korzeniem, a jego lewym i prawym dzieckiem są odpowiednio drzewa i ).

Ćwiczenie 12

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

Ćwiczenie 13

Niech i będą półgrupami. Sprawdź, czy półgrupami są także:

(1) , gdzie ,
(2) , gdzie i .

Ć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 i kongruencji taki, że ale jest skończona.

Ćwiczenie 16

Rozważmy monoid i ustalmy . Znajdź monoidy ilorazowe , gdzie relacja zdefiniowana jest następująco (najpierw sprawdź, czy jest kongruencją!):

wtw .

Ćwiczenie 17

Niech będzie dowolną półgrupą, a dowolnym podzbiorem . Udowodnij, że:

(1) relacja taka, że
jest lewą kongruencją,
(2) relacja taka, że
jest kongruencją.
Dla zainteresowanych

Ćwiczenie 18

W monoidzie wolnym rozważamy następujące podmonoidy:

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