Klasy abstrakcji indukowane przez język

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
rivit
Użytkownik
Użytkownik
Posty: 158
Rejestracja: 28 paź 2018, o 17:31
Płeć: Mężczyzna
Podziękował: 70 razy
Pomógł: 1 raz

Klasy abstrakcji indukowane przez język

Post autor: rivit » 21 maja 2020, o 00:23

Relacja \(\displaystyle{ R_L}\) jest relacją równoważności. Podać klasy abstrakcji relacji \(\displaystyle{ R_L}\) indukowanej przez język \(\displaystyle{ L}\) i wyznaczyć indeks (liczbę klas abstrakcji) relacji \(\displaystyle{ R_L}\).
(a) \(\displaystyle{ L = \left\{ 0^m10^k | k \ge 1, m \ge 1\right\}}\)

Jak robić takie zadania?
Potrzebuję jednego rozwiązania resztę wykminie sam, bo przykłady są podobne.
Pozdrawiam.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Jan Kraszewski
Administrator
Administrator
Posty: 26412
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4418 razy

Re: Klasy abstrakcji indukowane przez język

Post autor: Jan Kraszewski » 21 maja 2020, o 00:59

A może podasz definicję relacji \(\displaystyle{ R_L}\)?

JK

rivit
Użytkownik
Użytkownik
Posty: 158
Rejestracja: 28 paź 2018, o 17:31
Płeć: Mężczyzna
Podziękował: 70 razy
Pomógł: 1 raz

Re: Klasy abstrakcji indukowane przez język

Post autor: rivit » 21 maja 2020, o 10:22

Nie widze opcji edycji, dopiszę tutaj.

Relacją indukowaną przez język \(\displaystyle{ L \subseteq \Sigma^*}\) nazywamy relację \(\displaystyle{ R_L \subseteq \Sigma^* \times \Sigma^*}\) (gdzie \(\displaystyle{ \Sigma}\) jest skończonym niepustym alfabetem symboli) taką, że
\(\displaystyle{ \left(\forall u,v\in \Sigma^* \right) \left( u R_L v \Leftrightarrow \left(\left(\forall z \in \Sigma^* \right) \left(uz \in L \Leftrightarrow vz \in L \right) \right) \right) }\)

W tym zadaniu \(\displaystyle{ \Sigma = \left\{ 0, 1\right\} }\)

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 9006
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 1940 razy

Re: Klasy abstrakcji indukowane przez język

Post autor: Dasio11 » 21 maja 2020, o 10:25

Najprościej zacząć od napisania rozpoznającego ten język automatu o możliwie małej liczbie stanów.

rivit
Użytkownik
Użytkownik
Posty: 158
Rejestracja: 28 paź 2018, o 17:31
Płeć: Mężczyzna
Podziękował: 70 razy
Pomógł: 1 raz

Re: Klasy abstrakcji indukowane przez język

Post autor: rivit » 21 maja 2020, o 10:48

https://i.imgur.com/V2xaty2.png
Wstawiam jako link, bo obrazek jest szerszy niż 500px...

Narysowałem coś takiego, jednak nie wiem jak odczytać z tego klasy abstrakcji.

krl
Użytkownik
Użytkownik
Posty: 499
Rejestracja: 10 lis 2009, o 22:39
Płeć: Mężczyzna
Lokalizacja: Wrocław
Pomógł: 105 razy

Re: Klasy abstrakcji indukowane przez język

Post autor: krl » 21 maja 2020, o 11:16

Jeśli słowa \(\displaystyle{ v,w}\) są takie, że automat po przeczytaniu każdego z nich znajduje się tym samym stanie, to są one w relacji \(\displaystyle{ R_L}\).
Stąd dostajesz górne ograniczenie na liczbę klas relacji \(\displaystyle{ R_L}\). Musisz jeszcze rozstrzygnąć, czy tych klas jednak nie jest mniej...

rivit
Użytkownik
Użytkownik
Posty: 158
Rejestracja: 28 paź 2018, o 17:31
Płeć: Mężczyzna
Podziękował: 70 razy
Pomógł: 1 raz

Re: Klasy abstrakcji indukowane przez język

Post autor: rivit » 21 maja 2020, o 11:49

Wyszło mi coś takiego:

\(\displaystyle{ K_1 = \left\{ 0^m | m \ge 1 \right\} }\)
\(\displaystyle{ K_2 = \left\{ 0^m1 | m \ge 1 \right\} }\)
\(\displaystyle{ K_3 = \left\{ 0^m10^k | m \ge 1, k \ge 1 \right\} }\)
\(\displaystyle{ K_4 = \left\{ 0, 1\right\}^* - \left( K_1 \cup K_2 \cup K_3 \right) }\)


Zastanawia mnie jednak to, bo jak miałem taki język:
\(\displaystyle{ L = \left\{ 0^m1b^k | m, k \ge 0\right\} }\)
to klasy abstrakcji były następujące:
\(\displaystyle{ K_1 = \left\{ 0^m | m \ge 0 \right\} }\)
\(\displaystyle{ K_2 = \left\{ 0^m10^k | m, k \ge 0 \right\} }\)
\(\displaystyle{ K_3 = \left\{ 0, 1\right\}^* - \left( K_1 \cup K_2\right) }\)

Jednak w pierwotnym przykładzie są stany, które wymagają, żeby było np. zero minimum jeden raz. Jak to się ma do klas abstrakcji

Dodano po 1 dniu 9 godzinach 28 minutach 26 sekundach:
Czy komuś coś wiadomo na ten temat? :D

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 9006
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 1940 razy

Re: Klasy abstrakcji indukowane przez język

Post autor: Dasio11 » 22 maja 2020, o 21:52

Dla każdego stanu \(\displaystyle{ q_i}\) w automacie znajdź słowo \(\displaystyle{ u_i}\), które do niego prowadzi. Jeśli wszystkie te słowa będą parami nierównoważne, to automat jest optymalny i jego stany wyznaczają szukane klasy abstrakcji. A jeśli pewne dwa słowa są równoważne, to znaczy że automat jest nieoptymalny, tzn. istnieje automat o mniejszej liczbie stanów rozpoznający ten sam język. Wtedy możesz uprościć automat i powtarzać procedurę do skutku.

Na razie Twoja odpowiedź jest nieprawidłowa.

Odnośnie różnicy między oryginalnym zadaniem a podanym wyżej wariantem: niech \(\displaystyle{ L_1 = \{ 0^m 1 0^k | m \ge 1, k \ge 1 \}}\) i \(\displaystyle{ L_2 = \{ 0^m 1 0^k | m \ge 0, k \ge 0 \}}\). Wtedy słowa \(\displaystyle{ u = \varepsilon, v = 0}\) są w relacji \(\displaystyle{ R_{L_2}}\), bo liczba zer na początku słowa nie ma znaczenia. Ale te same słowa nie są w relacji \(\displaystyle{ R_{L_1}}\), bo słowa z dodatnią liczbą zer na początku mogą być akceptowane, a słowa bez zer - nie mogą. A konkretnie: słowo \(\displaystyle{ z = 10}\) świadczy o nierównoważności \(\displaystyle{ u}\) i \(\displaystyle{ v}\), bo \(\displaystyle{ uz = 10}\) nie należy do języka, a \(\displaystyle{ vz = 010}\) już należy.

Bardzo dobrym sposobem na ogarnięcie tego tematu jest zrozumienie dowodu twierdzenia o indeksie, bo ten dowód dokładnie opisuje związek między stanami w automacie a klasami abstrakcji rzeczonej relacji.

rivit
Użytkownik
Użytkownik
Posty: 158
Rejestracja: 28 paź 2018, o 17:31
Płeć: Mężczyzna
Podziękował: 70 razy
Pomógł: 1 raz

Re: Klasy abstrakcji indukowane przez język

Post autor: rivit » 23 maja 2020, o 12:02

Napisałem takiego długiego posta i mnie wylogowało i wyczyściło cały formualrz... Ehh...
Nie będę pisać od nowa, dlatego w skrócie.

\(\displaystyle{ K_1 = \left\{ 1^m | m \ge 0 \right\}}\)
bo do pierwszego stanu trafią wszystkie słowa, które nie będą zawierac zera.

\(\displaystyle{ K_2 = \left\{ 1^m0^k | m \ge 0, k \ge 1 \right\}}\)
Bo w drugim stanie bedą słowa typu: \(\displaystyle{ 111110, 111000, 1000, 0000}\)

\(\displaystyle{ K_3 = \left\{ 1^m0^k1^n | m \ge 0, k,n \ge 1 \right\}}\)
słowa postaci: \(\displaystyle{ 1111101, 1110001, 1000111, 00001111, 101, 01}\)

\(\displaystyle{ K_4 = \left\{ 1^m0^k1^n0^p | m \ge 0, k,n,p \ge 1 \right\}}\)
słowa postaci: \(\displaystyle{ 111110111000, 1110001000, 10001110, 0000111100, 10100, 0100}\)
i to jest stan akceptujący. Tylko, że widze, że tutaj trafiają słowa, które nie należą do języka.

\(\displaystyle{ K_5 = \left\{ 0, 1\right\}^* - \left( K_1 \cup K_2 \cup K_3 \cup K_4 \right)}\)
czyli pozostale

Niestety nie mam pojęcia, jak to poprawić i czy to w ogóle jest dobrze. Prosze o jakieś korekty.

Jan Kraszewski
Administrator
Administrator
Posty: 26412
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4418 razy

Re: Klasy abstrakcji indukowane przez język

Post autor: Jan Kraszewski » 23 maja 2020, o 13:41

rivit pisze:
23 maja 2020, o 12:02
Napisałem takiego długiego posta i mnie wylogowało i wyczyściło cały formualrz... Ehh...
Ech..

To przykre, ale w przyszłości warto zabezpieczać się - albo zapisywać kopię roboczą (jest taka opcja), albo - PRZED wysłaniem posta (jeżeli naprawdę długo go pisaliśmy) - otworzyć stronę forum w tej samej przeglądarce w innym oknie, sprawdzając czy nas nie wylogowało. Jeśli wylogowało, to zalogować się w tym nowym oknie. Wtedy próba wysłania posta spotka się z reakcją "Formularz nieaktualny...", ale powtórne wysłanie posta już zadziała.

JK

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 9006
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 1940 razy

Re: Klasy abstrakcji indukowane przez język

Post autor: Dasio11 » 23 maja 2020, o 22:33

Twój automat jest prawie dobry (brakuje dwóch strzałek odpowiadających jedynce), ale klasy abstrakcji już nie. Zacznij od poprawienia automatu, bo pewnie to jest źródłem niektórych błędów. W razie gdyby nadal wychodziła Ci ta sama odpowiedź - zastanów się, czy rzeczywiście po wczytaniu słowa \(\displaystyle{ 111}\) automat będzie w tym samym stanie co na początku?

rivit
Użytkownik
Użytkownik
Posty: 158
Rejestracja: 28 paź 2018, o 17:31
Płeć: Mężczyzna
Podziękował: 70 razy
Pomógł: 1 raz

Re: Klasy abstrakcji indukowane przez język

Post autor: rivit » 23 maja 2020, o 23:38

https://i.imgur.com/T3XqPo0.png
Poprawiony automat. Dodałem takie przejścia, które przenoszą nas do dead state gdy napotkamy nieprawidłowość.

Jednak klasy abstrakcji wychodzą mi identyczne jak pisałem wcześniej.

\(\displaystyle{ K_1 = \left\{ 0^m | m \ge 1 \right\}\\
K_2 = \left\{ 0^m1 | m \ge 1 \right\}\\
K_3 = \left\{ 0^m10^k | m \ge 1, k \ge 1 \right\}\\
K_4 = \left\{ 0, 1\right\}^* - \left( K_1 \cup K_2 \cup K_3 \right)}\)


Nie mam absolutnie innego pomysłu jak by to miało wyglądać. Uważam, że powyższa odpowiedź jest poprawna, jeśli nie jest proszę tym razem wskazać co konkretnie jest nie tak, gdyż nie mogę tego pojąć.

Dodano po 11 godzinach 39 minutach 49 sekundach:
Po głębszym namyśle dodałbym jezcze jedną klasę, która zawiera tylko słowo puste.

\(\displaystyle{ K_0 = \left\{ \epsilon \right\}}\)

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 9006
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 1940 razy

Re: Klasy abstrakcji indukowane przez język

Post autor: Dasio11 » 24 maja 2020, o 12:02

Włącznie z ostatnią klasą - odpowiedź jest poprawna (przy czym też trzeba ją odjąć od \(\displaystyle{ K_4}\)).

rivit
Użytkownik
Użytkownik
Posty: 158
Rejestracja: 28 paź 2018, o 17:31
Płeć: Mężczyzna
Podziękował: 70 razy
Pomógł: 1 raz

Re: Klasy abstrakcji indukowane przez język

Post autor: rivit » 24 maja 2020, o 12:20

Nie można było tak od razu? :D
Dzięki ;)

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 9006
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 1940 razy

Re: Klasy abstrakcji indukowane przez język

Post autor: Dasio11 » 24 maja 2020, o 12:26

Musiałem wcześniej źle popatrzeć, bo zdawało mi się, że jest więcej błędów.

ODPOWIEDZ