Iloraz prawostronny - czym właściwie jest ?

[Gdziemojekonie]

Czym właściwie jest iloraz prawostronny ?
Wpisując w google nie można otrzymać żadnych satysfakcjonujących odpowiedzi, a jedynie kilka pdfów z różnych uczelni, w których nie znalazłem wytłumaczenia tego zagadnienia.
Domyślam sie, że jest to operacja na zbiorach, ale po co ją robimy, w jakim celu ?
Czy ktoś jest potrafi wytłumaczyć na jakimś prostym przykładzie co to takiego ?

[Jan Kraszewski]

A ja wziąłem pierwszy pdf i znalazłem definicję:

\(\displaystyle{ LM^{-1}=\{v:(\exists w\in M)\,vw\in L\}.}\)

To jest operacja na językach. Jeśli ilorazujesz prawostronnie \(\displaystyle{ L}\) przez \(\displaystyle{ M}\) to patrzysz, które słowa z \(\displaystyle{ L}\) kończą się słowem, które jest w \(\displaystyle{ M}\) (mają sufiksy z \(\displaystyle{ M}\)) i wyrzucasz tę końcówkę (czyli sufiks). Iloraz tworzą te początki, które zostaną.

JK

[Gdziemojekonie]

Tylko nie wiem jak wywnioskować z tej definicji to:

Mam wyrażenie regularne:

\(\displaystyle{ 0 ^{*}1\left( 01\right) ^{*}}\)

i do tego oblicznia ilorazu prawostronnego

\(\displaystyle{ L//e \\
L//0 \\
L//1 \\
L//01 \\
L//11 \\
L//100}\)

Skąd biorą się symbole z prawej strony np. \(\displaystyle{ 11, 100, 01, 0}\) ?
Skąd mam wiedzieć przez jakie symbole mam dzielić i w jakiej kolejności?

[Jan Kraszewski]

No tutaj masz akurat dzielenie języka przez słowo (co odpowiada dzieleniu przez język jednoelementowy).

Skąd biorą się symbole z prawej strony np. \(\displaystyle{ 11, 100, 01, 0}\) ?

Z treści zadania. Masz dany język, zadany przez wyrażenie regularne, masz dane słowo i masz wykonać dzielenie.

Skąd mam wiedzieć przez jakie symbole mam dzielić i w jakiej kolejności?

Z treści zadania...

Mam wyrażenie regularne:

\(\displaystyle{ 0 ^{*}1\left( 01\right) ^{*}}\)

i do tego oblicznia ilorazu prawostronnego

\(\displaystyle{ L//e \\
L//0 \\
L//1 \\
L//01 \\
L//11 \\
L//100}\)

Np. żeby wyznaczyć \(\displaystyle{ L//1}\) musisz w języku \(\displaystyle{ L}\) znaleźć wszystkie słowa, które kończą się na \(\displaystyle{ 1}\) i jako wynik dzielenia otrzymasz zbiór tych słów, które powstaną z tych znalezionych po usunięciu tej końcowej jedynki.

JK

[Gdziemojekonie]

Z treści zadania. Masz dany język, zadany przez wyrażenie regularne, masz dane słowo i masz wykonać dzielenie.

Szczerze mówiąc, w treści zadania widzę tylko język opisany wyrażeniem regularnym.
Gdzie mam dane słowo ? Jak je Pan wyciągnął z wyrażenia regularnego ?

Czy chodzi o to, żebym sam wyznaczył wszystkie słowa należące do tego języka, a następnie język dzielił przez te wszystkie słowa zaczynając od najkrótszych ?

[Jan Kraszewski]

Szczerze mówiąc, w treści zadania widzę tylko język opisany wyrażeniem regularnym.
Gdzie mam dane słowo ? Jak je Pan wyciągnął z wyrażenia regularnego ?

Żeby policzyć iloraz, musisz mieć dzielną i dzielnik, inaczej się nie da...

No ja widzę

\(\displaystyle{ L//e \\
L//0 \\
L//1 \\
L//01 \\
L//11 \\
L//100}\)

co według mnie oznacza, że masz podzielić \(\displaystyle{ L}\) przez \(\displaystyle{ e}\), potem podzielić \(\displaystyle{ L}\) przez \(\displaystyle{ 0}\) itd., czyli masz sześć ilorazów do policzenia.

JK

[Gdziemojekonie]

To jest właśnie punkt kulminacyjny mojego pytania(skąd brać dzielniki), bowiem to:

\(\displaystyle{ L//e \\
L//0 \\
L//1 \\
L//01 \\
L//11 \\
L//100}\)

.. + jeszcze kolejne, ale wkleiłem tylko część.

jest podane już jako element rozwiązania, właśnie ciekawi mnie, skąd autor je wziął, bo są kolejne zadania, z innymi wyrażeniami i są rózne dzielniki dla nich w rozwiązaniach.

Oryginalna treść zadania:

Skonstruować graf stanów (lub podać funkcję przejść) deterministycznego automatu o minimalnej liczbie stanów, który akceptuje język opisany następującym wyrażeniem regularnym: \(\displaystyle{ L = 0^*1(01)^*}\).

a po tym

Rozwiązanie:

i autor dzieli sobie przez dzielniki, które nie wiem skąd wziął.

[Jan Kraszewski]

Oryginalna treść zadania:

Skonstruować graf stanów (lub podać funkcję przejść) deterministycznego automatu o minimalnej liczbie stanów, który akceptuje język opisany następującym wyrażeniem regularnym: \(\displaystyle{ L = 0*1(01)*}\).

No to fajnie, że w czwarty poście podałeś w końcu treść zadania... Twoje pierwotne pytanie dotyczyło ilorazu prawostronnego, a nie grafu stanów automatu deterministycznego.

A na pytanie dotyczące grafu stanów niestety Ci nie odpowiem. Choć podejrzewam, że dzielniki biorą się z jakiegoś standardowego algorytmu.

JK

[Dasio11]

Na podstawie podanych przez Ciebie informacji trudno stwierdzić, skąd się wzięły dzielniki. Być może byłoby to możliwe, gdybyś przytoczył rozwiązanie, ale mogę też pozgadywać.

Deterministyczny automat skończony o najmniejszej możliwej liczbie stanów, rozpoznający \(\displaystyle{ L}\) jest ściśle związany z relacją równoważności \(\displaystyle{ \sim}\) na \(\displaystyle{ \Sigma^*}\) określoną następująco: dla \(\displaystyle{ u, v \in \Sigma^*}\)

\(\displaystyle{ u \sim v \text{ gdy } (\forall w \in \Sigma^*) \, (uw \in L \Leftrightarrow vw \in L).}\)

Dokładniej: twierdzenie o indeksie mówi, że język \(\displaystyle{ L}\) jest regularny wtedy i tylko wtedy, gdy liczba klas abstrakcji relacji \(\displaystyle{ \sim}\) jest skończona, a co więcej, liczba klas to najmniejsza możliwa liczba stanów automatu rozpoznającego \(\displaystyle{ L}\). Twierdzenie mówi też, jak taki automat skonstruować, jeśli znamy klasy abstrakcji.

Definicję \(\displaystyle{ \sim}\) można równoważnie przepisać w terminach ilorazów:

\(\displaystyle{ u \sim v \iff (\forall w \in \Sigma^*) \, (u \in L/w \Leftrightarrow v \in L/w).}\)

Stąd zapewne wyznaczanie kilku przykładowych ilorazów \(\displaystyle{ L / \varepsilon, L/0, L/11}\), itd. Każde słowo \(\displaystyle{ w}\) dzieli \(\displaystyle{ \Sigma^*}\) na dwa podzbiory: \(\displaystyle{ L/w}\) i dopełnienie. Podział \(\displaystyle{ \Sigma^*}\) na klasy abstrakcji będzie wspólnym rozdrobnieniem takich partycji po wszystkich \(\displaystyle{ w \in \Sigma^*}\).