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: 163
Rejestracja: 28 paź 2018, o 17:31
Płeć: Mężczyzna
Podziękował: 70 razy
Pomógł: 2 razy

Klasy abstrakcji indukowane przez język

Post autor: rivit »

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.
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Klasy abstrakcji indukowane przez język

Post autor: Jan Kraszewski »

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

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

Re: Klasy abstrakcji indukowane przez język

Post autor: rivit »

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: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Klasy abstrakcji indukowane przez język

Post autor: Dasio11 »

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: 163
Rejestracja: 28 paź 2018, o 17:31
Płeć: Mężczyzna
Podziękował: 70 razy
Pomógł: 2 razy

Re: Klasy abstrakcji indukowane przez język

Post autor: rivit »

Kod: Zaznacz cały

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: 609
Rejestracja: 10 lis 2009, o 22:39
Płeć: Mężczyzna
Lokalizacja: Wrocław
Pomógł: 135 razy

Re: Klasy abstrakcji indukowane przez język

Post autor: krl »

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: 163
Rejestracja: 28 paź 2018, o 17:31
Płeć: Mężczyzna
Podziękował: 70 razy
Pomógł: 2 razy

Re: Klasy abstrakcji indukowane przez język

Post autor: rivit »

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: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Klasy abstrakcji indukowane przez język

Post autor: Dasio11 »

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: 163
Rejestracja: 28 paź 2018, o 17:31
Płeć: Mężczyzna
Podziękował: 70 razy
Pomógł: 2 razy

Re: Klasy abstrakcji indukowane przez język

Post autor: rivit »

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: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Klasy abstrakcji indukowane przez język

Post autor: Jan Kraszewski »

rivit pisze: 23 maja 2020, o 12:02Napisał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: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Klasy abstrakcji indukowane przez język

Post autor: Dasio11 »

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: 163
Rejestracja: 28 paź 2018, o 17:31
Płeć: Mężczyzna
Podziękował: 70 razy
Pomógł: 2 razy

Re: Klasy abstrakcji indukowane przez język

Post autor: rivit »

Kod: Zaznacz cały

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: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Klasy abstrakcji indukowane przez język

Post autor: Dasio11 »

Włącznie z ostatnią klasą - odpowiedź jest poprawna (przy czym też trzeba ją odjąć od \(\displaystyle{ K_4}\)).
rivit
Użytkownik
Użytkownik
Posty: 163
Rejestracja: 28 paź 2018, o 17:31
Płeć: Mężczyzna
Podziękował: 70 razy
Pomógł: 2 razy

Re: Klasy abstrakcji indukowane przez język

Post autor: rivit »

Nie można było tak od razu? :D
Dzięki ;)
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Klasy abstrakcji indukowane przez język

Post autor: Dasio11 »

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