Alfabet i liczba klas abstrakcji

[vicossess]

Dostałem następujące zadanie:
Niech \(\displaystyle{ \Sigma}\) będzie skończonym zbiorem symboli (alfabetem) oraz niech \(\displaystyle{ L \subseteq \Sigma^{*}}\). Relacja \(\displaystyle{ \sim_L \subseteq \Sigma^{*} \times \Sigma^{*}}\) jest zdefiniowana w następujący sposób \(\displaystyle{ v \sim_L v'}\) wtedy i tylko wtedy, gdy dla każdego \(\displaystyle{ x \in \Sigma^{*} ( vx \in L \Leftrightarrow v'x \in L)}\). Analogicznie zdefiniowana jest relacja \(\displaystyle{ \sim_L^{inf}}\) z tym, że \(\displaystyle{ v \sim_L^{inf} v'}\) wtedy i tylko wtedy, gdy dla każdych \(\displaystyle{ x, y \in \Sigma^{*} ( xvy \in L \Leftrightarrow xv'y \in L)}\).

\(\displaystyle{ i_L}\) to liczba klas abstrakcji na jakie relacja \(\displaystyle{ \sim_L}\) dzieli \(\displaystyle{ \Sigma^{*}}\), analogicznie jest określone \(\displaystyle{ i_L^{inf}}\)

Pokazać, że jeśli \(\displaystyle{ \arrowvert \Sigma \arrowvert = 1}\) to \(\displaystyle{ i_L = i_L^{inf}}\)

I ogólnie mam parę pytań, czy dobrze pojmuję istotę zadania:

1. \(\displaystyle{ \Sigma}\) ma jeden znak (powiedzmy, że to jest \(\displaystyle{ \alpha}\)), natomiast \(\displaystyle{ \Sigma^{*}}\) to są wszystkie słowa utworzone z danego alfabetu - czy dobrze myślę, że \(\displaystyle{ \arrowvert \Sigma^{*} \arrowvert = 2}\)? (tj. jedynymi słowami, które mogą być utworzone, to słowo puste i \(\displaystyle{ \alpha}\)? Czy przykładowo mogę powiedzieć, że jest nieskończenie wiele słów w \(\displaystyle{ \Sigma^{*}}\), ponieważ jeśli \(\displaystyle{ \alpha}\) jest słowem, to \(\displaystyle{ \alpha\alpha}\) też nim jest?)

2. Jeśli \(\displaystyle{ \arrowvert \Sigma^{*} \arrowvert = 2}\) (tj. pierwsza część 1 pytania jest prawdziwa) to czy w takim razie \(\displaystyle{ \arrowvert \sim_L \arrowvert = 4}\)?

3. Czy w przypadku relacji \(\displaystyle{ \sim_L}\) klasami abstrakcji będą początki słów?

4. Ostatecznie, czy moje pytania mają jakikolwiek sens przy rozważaniu tego zadania, czy powinienem zmienić podejście do problemu? (Mam przynajmniej nadzieję, że chociaż nie są bezsensowne)

[Dasio11]

1. Jeśli \(\displaystyle{ \Sigma = \{ \alpha \},}\) to

\(\displaystyle{ \Sigma^* = \{ \varepsilon, \alpha, \alpha \alpha, \alpha \alpha \alpha, \ldots \} = \{ \alpha^n : n \in \NN \},}\)

czyli \(\displaystyle{ \Sigma^*}\) jest nieskończony.

2. Poprzednik jest fałszywy, więc zgaduję, że pytanie jest nieaktualne. Ale gdyby był prawdziwy, to tak by zdecydowanie nie mogło być: \(\displaystyle{ \sim_L}\) jest relacją równoważności na dwuelementowym zbiorze \(\displaystyle{ \Sigma^*.}\) Taka relacja nie może mieć czterech klas abstrakcji, bo klas abstrakcji zawsze jest najwyżej tyle, co elementów.

3. Nie, klasy abstrakcji to klasy abstrakcji - czyli jakieś podzbiory \(\displaystyle{ \Sigma^*,}\) parami rozłączne i w sumie pokrywające zbiór \(\displaystyle{ \Sigma^*.}\) Pewne słowa mogą być wygodnymi w użyciu reprezentantami (czyli elementami) klas abstrakcji, ale takich kanonicznych reprezentantów nie zawsze da się wyróżnić.


Podpowiedź: zauważ, że warunek określający relację \(\displaystyle{ \sim_L^{\inf }}\) jest silniejszy od warunku określającego relację \(\displaystyle{ \sim_L,}\) co można zobaczyć, podstawiając w tym pierwszym \(\displaystyle{ x = \varepsilon.}\) Stąd zawsze (czyli nawet bez założenia, że \(\displaystyle{ |\Sigma| = 1}\)) będzie \(\displaystyle{ \sim_L^{\inf } \subseteq \sim_L,}\) czyli relacja \(\displaystyle{ \sim_L^{\inf }}\) indukuje podział \(\displaystyle{ \Sigma^*}\) na drobniejsze klasy abstrakcji.
Spróbuj pokazać, że gdy \(\displaystyle{ \Sigma = \{ \alpha \},}\) to zachodzi też zawieranie w drugą stronę, zatem te relacje są równe i mają tyle samo klas abstrakcji.

[vicossess]

To jeszcze mam dwie sprawy:
Pierwsza sprawa jest następująca - spotkałem się z trzema definicjami domknięcia tranzytywnego relacji \(\displaystyle{ R}\) - tj. jedną słowną - Jest to najmniejszy zbiór przechodni zawierający relację \(\displaystyle{ R}\).
Drugą w takiej postaci: \(\displaystyle{ R^{+} = \bigcup_{i = 0}^{} R^{i}}\)
a trzecią w takiej: \(\displaystyle{ R^{+} = \bigcap \tau}\) gdzie \(\displaystyle{ \tau = \left\{ S \subseteq A^2 \arrowvert S}\) jest przechodnia \(\displaystyle{ \wedge R \subseteq S \right\}}\). Z jednej strony te wszystkie definicje są równoważne i to jest w miarę jasne - według trzeciej mamy część wspólną wszystkich relacji przechodnich zawierających R, czyli rzeczywiście znajduje się tam nasze domknięcie przechodnie. Według drugiej tak iterujemy relacje i do siebie dodajemy, żeby stworzyły domknięcie tranzytywne (na mocy np. tego, że \(\displaystyle{ R}\) jest przechodnie \(\displaystyle{ \Leftrightarrow RR \subseteq R}\)).

Czy takie wytłumaczenie wystarcza do dowodu, że definicje te są równoważne? Czy istnieje jakiś 'bardziej formalny' dowód? (Czy domknięciem przechodnim relacji przechodniej jest ona sama? - w sumie to ma sens, zważając na fakt, że nie ma po co 'domykać przechodnio' relacji przechodniej, bo nie ma czego domykać)

Druga sprawa odnosi się do zadania powyżej:
Gdy mam \(\displaystyle{ L \subseteq \Sigma^{*}}\) takie, że \(\displaystyle{ L = \left\{ \alpha\alpha, \alpha\beta \right\}}\) to czy w tym przypadku mam \(\displaystyle{ \arrowvert \sim_L \arrowvert = 4}\) ?
(tj. istnieją 4 pary uporządkowane, które spełniają relację L i wtedy \(\displaystyle{ \sim_L = \left\{ \left\langle \alpha\beta,\alpha\beta \right\rangle, \left\langle \beta\beta,\alpha\beta \right\rangle, \left\langle \alpha\beta, \beta\beta \right\rangle, \left\langle \beta\beta, \beta\beta \right\rangle \right\}}\)?

Czy da się tutaj wyróżnić reprezentantów klas abstrakcji w jakikolwiek sposób? Ile wynosi wtedy \(\displaystyle{ i_L}\)? Czy wtedy \(\displaystyle{ i_L = 1}\)?

[Dasio11]

1. Moim zdaniem to za mało.

Oznaczmy tak:

\(\displaystyle{ R_1}\) - najmniejsza relacja przechodnia zawierająca \(\displaystyle{ R,}\)

\(\displaystyle{ R_2 = \bigcup_{i=1}^{\infty} R^i}\) (sumowanie jest od \(\displaystyle{ i=1,}\) bo inaczej dostaniemy domknięcie przechodnie i zwrotne)

\(\displaystyle{ R_3 = \bigcap \tau}\) gdzie \(\displaystyle{ \tau = \{ S \subseteq A^2 | S \text{ jest przechodnia oraz } R \subseteq S \}.}\)


Twój pierwszy argument jest taki, że \(\displaystyle{ R_1 \in \tau,}\) wobec tego \(\displaystyle{ R_3 \subseteq R_1.}\)

Twój drugi argument jest mniej jasno sformułowany, ale pewnie masz na myśli, że \(\displaystyle{ R_2}\) jest zawierającą \(\displaystyle{ R}\) relacją przechodnią (to przydałoby się lepiej uzasadnić), więc \(\displaystyle{ R_1 \subseteq R_2.}\)

Teraz czego brakuje: po pierwsze, relacje \(\displaystyle{ R_2}\) i \(\displaystyle{ R_3}\) są dobrze zdefiniowane, ale \(\displaystyle{ R_1}\) ma być najmniejszą relacją o pewnej własności - trzeba więc pokazać, że ta definicja jest dobra, czyli że wśród relacji o tej własności rzeczywiście istnieje dokładnie jeden element najmniejszy. Po drugie, jak łatwo zauważyć, brakuje trzeciego zawierania \(\displaystyle{ R_2 \subseteq R_3.}\)

Proponuję jednak zacząć od początku i zrobić tak: pokazać, że \(\displaystyle{ R_2}\) i \(\displaystyle{ R_3}\) spełniają definicję pierwszą oraz że relacja spełniająca definicję pierwszą może być najwyżej jedna - wtedy jednocześnie pokażemy, że \(\displaystyle{ R_1}\) jest dobrze zdefiniowana oraz \(\displaystyle{ R_2 = R_1}\) i \(\displaystyle{ R_3 = R_1,}\) czyli to, co chcemy. Myślę, że tak jest klarowniej.

Podsumowując, trzeba pokazać, że:

\(\displaystyle{ \bullet \, R_2}\) jest najmniejszym (ze względu na zawieranie) elementem \(\displaystyle{ \tau,}\)

\(\displaystyle{ \bullet \, R_3}\) jest najmniejszym elementem \(\displaystyle{ \tau,}\)

\(\displaystyle{ \bullet}\) Dla dowolnych relacji \(\displaystyle{ R', R'' \subseteq A^2,}\) jeśli \(\displaystyle{ R'}\) i \(\displaystyle{ R''}\) są najmniejszymi elementami \(\displaystyle{ \tau,}\) to \(\displaystyle{ R' = R''}\) (to jest na jedną linijkę).

Odnośnie pytania: zgadza się, domknięciem przechodnim relacji przechodniej jest ona sama.


2. Nie, no skąd.

Relacja \(\displaystyle{ \sim_L \subseteq \Sigma^* \times \Sigma^*}\) jest relacją równoważności, więc w szczególności jest zwrotna, czyli dla każdego \(\displaystyle{ w \in \Sigma^*}\) mamy \(\displaystyle{ \left< w, w \right> \in \sim_L}\) - relacja jest więc nieskończona.

Relacja jest zdefiniowana w sposób na pierwszy rzut oka nieprzejrzysty, więc trudno od razu zrozumieć, jak ona działa. W takim przypadku klas abstrakcji najłatwiej szukać tak: wybieramy losowy element \(\displaystyle{ u \in \Sigma^*}\) i próbujemy wymyślić, z jakimi innymi elementami jest on w relacji \(\displaystyle{ \sim_L.}\) Po drodze dowodzimy wszystkich swoich przypuszczeń. Wtedy znamy już jedną klasę abstrakcji: \(\displaystyle{ _{\sim_L}.}\) Jeśli jest ona całym \(\displaystyle{ \Sigma^*,}\) to koniec, a jeśli nie, to znajdujemy element \(\displaystyle{ v \in \Sigma^* \setminus _{\sim_L}}\) i znów szukamy, z czym on jest w relacji, w efekcie wyznaczając jego klasę abstrakcji. W ten sposób postępujemy do momentu, w którym znalezione klasy abstrakcji sumują się do \(\displaystyle{ \Sigma^*,}\) co oznacza, że to już wszystkie.

Na przykład: weźmy \(\displaystyle{ u = \varepsilon.}\) Szukamy wszystkich takich \(\displaystyle{ u' \in \Sigma^*,}\) że \(\displaystyle{ \varepsilon \sim_L u',}\) czyli że dla dowolnego \(\displaystyle{ y \in \Sigma^*}\) jest \(\displaystyle{ y \in L \iff u' y \in L.}\) Po chwili namysłu można dojść do wniosku, że dobrze jest podstawić \(\displaystyle{ y = \alpha \alpha}\) i wtedy ma zachodzić \(\displaystyle{ \alpha \alpha \in L \iff u' \alpha \alpha \in L.}\) Lewa strona jest prawdziwa, więc prawa też musi być, ale jest ona prawdziwa tylko dla \(\displaystyle{ u' = \varepsilon,}\) toteż \(\displaystyle{ [\varepsilon]_{\sim_L} = \{ \varepsilon \}}\) - klasa abstrakcji słowa pustego jest jednoelementowa.


W przypadku tej właśnie relacji istnieje jednak bardziej efektywna metoda. Ma ona bowiem ścisły związek z tak zwanym twierdzeniem o indeksie dla deterministycznych automatów skończonych (DFA), więc przypuszczam, że coś Ci o nich wiadomo. Twierdzenie to mówi, że język \(\displaystyle{ L}\) jest regularny wtedy i tylko wtedy, gdy relacja \(\displaystyle{ \sim_L}\) ma skończenie wiele klas abstrakcji, a wówczas liczba tych klas to najmniejsza liczba stanów w DFA rozpoznającym \(\displaystyle{ L.}\) Ponadto optymalny DFA (czyli ten o najmniejszej liczbie stanów) ma bardzo przejrzystą budowę: jego stanami są klasy abstrakcji, a dla każdego \(\displaystyle{ u \in \Sigma^*}\) oraz \(\displaystyle{ a \in \Sigma}\) mamy przejście \(\displaystyle{ _{\sim_L} = q_1 \xrightarrow{a} q_2 = [ua]_{\sim_L}.}\) Stanem początkowym jest \(\displaystyle{ q_0 = [\varepsilon]_{\sim_L}}\) a stany akceptujące to \(\displaystyle{ _{\sim_L}}\) takie że \(\displaystyle{ u \in L.}\)
Jeśli to, o czym mówię, nie jest Ci obce - spróbuj zbudować DFA rozpoznający \(\displaystyle{ L = \{ \alpha \alpha, \alpha \beta \}}\) o jak najmniejszej liczbie stanów i z niego wywnioskować, jak wyglądają klasy abstrakcji: jeśli Twój automat będzie dobry, to będzie zachodziła równoważność

\(\displaystyle{ u \sim_L v \iff \hat{\delta}( u, q_0 ) = \hat{\delta}( v, q_0 ),}\)

więc klasy abstrakcji będą indeksowane stanami \(\displaystyle{ q}\) tego automatu i będą postaci

\(\displaystyle{ \{ u \in \Sigma^* : \hat{\delta}( u, q_0 ) = q \}.}\)