Matematyka.pl

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 ?

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

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?

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

Gdziemojekonie pisze: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.

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

Z treści zadania...

Gdziemojekonie pisze: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

Jan Kraszewski pisze: 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 ?

Gdziemojekonie pisze: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ę

Gdziemojekonie pisze:\(\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

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ął.

Gdziemojekonie pisze: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

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^*}\).