Witam. Mam następujący problem.
Dostałem do rozwiązania z teoretycznych podstaw informatyki następujące zadanie:
W hotelu jest K pięter. Przejazd windy bez zatrzymania z piętra i na piętro\(\displaystyle{ j (i \neq j)}\) uważamy za jednostkową akcję. Z każdą taką akcją wiążemy literę: G jeśli \(\displaystyle{ i < j}\), D jeśli \(\displaystyle{ i > j}\). Rozważamy możliwe trasy windy, które rozpoczynają się i kończą na parterze. Każda taka trasa wyznacza słowo nad alfabetem \(\displaystyle{ {G, D}}\). Niech \(\displaystyle{ L \subseteq {G, D}^{*}}\) będzie zbiorem wszystkich tak otrzymanych słów. Pokazać, że język L jest regularny.
Nie ma problemu w przypadku udowodnienia że język ten jest nieregularny, problem jest w momencie że mam udowodnić że jest regularny. Według Pani profesor udowodnienie języka nieregularnego poprzez zastosowanie lematów nie wyklucza że jest regularny.
Proszę o pomoc
pozdrawiam
Problem z windą i językiem regularnym
-
Siergiej29
- Użytkownik
- Posty: 2
- Rejestracja: 11 wrz 2014, o 12:59
- Płeć: Mężczyzna
- Lokalizacja: Opole
-
Siergiej29
- Użytkownik
- Posty: 2
- Rejestracja: 11 wrz 2014, o 12:59
- Płeć: Mężczyzna
- Lokalizacja: Opole
Problem z windą i językiem regularnym
Widzę, że nikt nie potrafił mi pomóc. Na szczęście miałem dobrych kolegów z uczelni którzy mi pomogli.
Dla potomnych, przedstawię rozwiązanie zadania, które okazało się dosyć proste.
Mamy pokazać, że język L jest regularny.
Z Definicji języka regaularnego wynika, że aby język był regularny, należy stworzyć deterministyczny automat skończony. I koniec. Nie trzeba formułować całego języka który powstanie aby udowodnić regularność języka.
Teraz pytanie jak stworzyć taki automat?
Musimy przyjąć pewne zasady.
Posiadamy alfabet \(\displaystyle{ G}\) i \(\displaystyle{ D}\) z którego ma się składać język. \(\displaystyle{ G}\) i \(\displaystyle{ D}\) są to przejścia ze stanu \(\displaystyle{ A}\) do stanu \(\displaystyle{ B}\).
Przejazd windy bez zatrzymania z piętra i na piętroj \(\displaystyle{ (i \neq j)}\) uważamy za jednostkową akcję. Czyli jadąc z parteru na piętro 5, albo piętro 40, bądź na 100 to zapisujemy jedna litera \(\displaystyle{ G}\). Tak samo tyczy się jazdy windą na dół z piętra ostatniego możemy zatrzymać się na 40 jak i na parterze. Też to jednostkowa akcja zapisujemy ją jako \(\displaystyle{ D}\).
Zaczynamy przejazd z parteru i kończymy na parterze. Jak juz pewnie wiadomo pierwszą literą słowa będzie \(\displaystyle{ G}\) bo zaczynając z parteru możemy jechać tylko w górę. Ostatnim słowem będzie \(\displaystyle{ D}\).
Np: zaczynamy z parteru i jedziemy najpierw na piętro 5, potem na 12, następnie na 6 i na ostatnie \(\displaystyle{ k}\), powrotem na parter. Powstanie nam słowo \(\displaystyle{ GGDGD}\)
Całe zdanie można sobie wyobrazić jako ciąg znaków \(\displaystyle{ +}\) i \(\displaystyle{ -}\)
Za każdym znakiem musisz wpisać liczbę ale tak żeby cale wyrażenie było równe \(\displaystyle{ 0}\)
Ograniczeniem jest to że za każdym znakiem musi stać liczba przedziału \(\displaystyle{ <1,K>}\). Dodatkowo w żadnym momencie nie może przekroczyć sumą liczby K bo byśmy widną wiechali na dach.
A oto deterministyczny automat skończony.
Wszystkie stany po lewej są odrzucające dlatego ze jadąc ciągle w góre nigdy nie jesteś na parterze, a w pewnym momencie nie możesz już jechać dalej, ale każdy ruch w dol potencjalnie sciąga nas na sam parter. ale nie musi, dlatego liczy się teraz tylko to czy nie wykonamy ruchów w dół za dużo (więcej niż K) bo wtedy wpadamy do piwnicy.
Ten automat wie o ile najmniej może pojechać w góre lub w dól, i wie ile wynosi maksymalna trasa. pilnuje tez żeby przystanków w jedna stronę nie było za dużo, bo wie ze za każdym krokiem musi się przemieścić co najmniej o 1 piętro.
Zadanie poprawnie rozwiązane bo sprawdzone przez Pani profesor.
Dziękuje za "pomoc" i pozdrawiam.
Dla potomnych, przedstawię rozwiązanie zadania, które okazało się dosyć proste.
Mamy pokazać, że język L jest regularny.
Z Definicji języka regaularnego wynika, że aby język był regularny, należy stworzyć deterministyczny automat skończony. I koniec. Nie trzeba formułować całego języka który powstanie aby udowodnić regularność języka.
Teraz pytanie jak stworzyć taki automat?
Musimy przyjąć pewne zasady.
Posiadamy alfabet \(\displaystyle{ G}\) i \(\displaystyle{ D}\) z którego ma się składać język. \(\displaystyle{ G}\) i \(\displaystyle{ D}\) są to przejścia ze stanu \(\displaystyle{ A}\) do stanu \(\displaystyle{ B}\).
Przejazd windy bez zatrzymania z piętra i na piętroj \(\displaystyle{ (i \neq j)}\) uważamy za jednostkową akcję. Czyli jadąc z parteru na piętro 5, albo piętro 40, bądź na 100 to zapisujemy jedna litera \(\displaystyle{ G}\). Tak samo tyczy się jazdy windą na dół z piętra ostatniego możemy zatrzymać się na 40 jak i na parterze. Też to jednostkowa akcja zapisujemy ją jako \(\displaystyle{ D}\).
Zaczynamy przejazd z parteru i kończymy na parterze. Jak juz pewnie wiadomo pierwszą literą słowa będzie \(\displaystyle{ G}\) bo zaczynając z parteru możemy jechać tylko w górę. Ostatnim słowem będzie \(\displaystyle{ D}\).
Np: zaczynamy z parteru i jedziemy najpierw na piętro 5, potem na 12, następnie na 6 i na ostatnie \(\displaystyle{ k}\), powrotem na parter. Powstanie nam słowo \(\displaystyle{ GGDGD}\)
Całe zdanie można sobie wyobrazić jako ciąg znaków \(\displaystyle{ +}\) i \(\displaystyle{ -}\)
Za każdym znakiem musisz wpisać liczbę ale tak żeby cale wyrażenie było równe \(\displaystyle{ 0}\)
Ograniczeniem jest to że za każdym znakiem musi stać liczba przedziału \(\displaystyle{ <1,K>}\). Dodatkowo w żadnym momencie nie może przekroczyć sumą liczby K bo byśmy widną wiechali na dach.
A oto deterministyczny automat skończony.
Wszystkie stany po lewej są odrzucające dlatego ze jadąc ciągle w góre nigdy nie jesteś na parterze, a w pewnym momencie nie możesz już jechać dalej, ale każdy ruch w dol potencjalnie sciąga nas na sam parter. ale nie musi, dlatego liczy się teraz tylko to czy nie wykonamy ruchów w dół za dużo (więcej niż K) bo wtedy wpadamy do piwnicy.
Ten automat wie o ile najmniej może pojechać w góre lub w dól, i wie ile wynosi maksymalna trasa. pilnuje tez żeby przystanków w jedna stronę nie było za dużo, bo wie ze za każdym krokiem musi się przemieścić co najmniej o 1 piętro.
Zadanie poprawnie rozwiązane bo sprawdzone przez Pani profesor.
Dziękuje za "pomoc" i pozdrawiam.
Re: Problem z windą i językiem regularnym
Kurde,ma ktoś może ten obrazek DFA? potrzebuję żeby zaliczyć przedmiot!!! ważne
-
Dasio11
- Moderator
- Posty: 10218
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2361 razy
Re: Problem z windą i językiem regularnym
Wygląda na to, że obrazek przepadł, ale język opisany w zadaniu to dokładnie język złożony ze słowa pustego oraz takich słów niepustych, które zaczynają się od G, kończą się na D i w dodatku każdy spójny podciąg złożony z liter G ma długość nie większą niż \(\displaystyle{ K}\) i każdy spójny podciąg złożony z liter D ma długość nie większą niż \(\displaystyle{ K}\). Symbolicznie:
\(\displaystyle{ L = \left\{ G^{n_1} D^{n_2} \ldots G^{n_{2k-1}} D^{n_{2k}} : k \in \NN \cup \{ 0 \} \wedge \bigwedge_{i=1}^{2k} 1 \le n_i \le K \right\}}\)
Stosunkowo łatwo skonstruować automat, który rozpoznaje powyższy język.
\(\displaystyle{ \begin{tikzpicture}
\foreach \i in { 1, 2, 3 }
{
\draw ( 2*\i+1, 2 ) circle [radius=0.5];
\node at ( 2*\i+1, 2 ) {$g_\i$};
\draw [->] ( 2*\i+1.5, 2 ) -- ( 2*\i+2.5, 2 );
\node at ( 2*\i+1.5, 2 ) [above right] {$G$};
\draw ( 2*\i+1, 1.5 ) -- ( 2*\i+1, 0.5 );
\node at ( 2*\i+1, 1.5 ) [below right] {$D$};
}
\node at ( 9, 2 ) {$\ldots$};
\draw [->] ( 9.5, 2 ) -- ( 10.5, 2 );
\node at ( 9.5, 2 ) [above right] {$G$};
\draw ( 11, 2 ) circle [radius=0.5];
\node at ( 11, 2 ) {$g_{K}$};
\draw [->] ( 11.5, 2 ) -- ( 13, 2 ) -- ( 13, 0.5 );
\node at ( 11.5, 2 ) [above right] {$G$};
\draw [->] ( 11, 1.5 ) -- ( 11, 0.5 ) -- ( 1, 0.5 ) -- ( 1, -2 ) -- ( 2.5, -2 );
\node at ( 11, 1.5 ) [below right] {$D$};
\foreach \i in { 1, 2, 3 }
{
\draw ( 2*\i+0.5, -2.5 ) rectangle ( 2*\i+1.5, -1.5);
\node at ( 2*\i+1, -2 ) {$d_\i$};
\draw [->] ( 2*\i+1.5, -2 ) -- ( 2*\i+2.5, -2 );
\node at ( 2*\i+1.5, -2 ) [below right] {$D$};
\draw ( 2*\i+1, -1.5 ) -- ( 2*\i+1, -0.5 );
\node at ( 2*\i+1, -1.5 ) [above right] {$G$};
}
\node at ( 9, -2 ) {$\ldots$};
\draw [->] ( 9.5, -2 ) -- ( 10.5, -2 );
\node at ( 9.5, -2 ) [below right] {$D$};
\draw ( 10.5, -2.5 ) rectangle ( 11.5, -1.5);
\node at ( 11, -2 ) {$d_{K}$};
\draw [->] ( 11.5, -2 ) -- ( 13, -2 ) -- ( 13, -0.5 );
\node at ( 11.5, -2 ) [below right] {$D$};
\draw [->] ( 11, -1.5 ) -- ( 11, -0.5 ) -- ( 1.5, -0.5 ) -- ( 1.5, 2 ) -- ( 2.5, 2 );
\node at ( 11, -1.5 ) [above right] {$G$};
\draw ( 13, 0 ) circle [radius=0.5];
\node at ( 13, 0 ) {$q$};
\draw[->, bend left] ( 13.35, 0.35 ) to [out=45, in=110] ( 14.25, 0 ) to [out=70, in=135] ( 13.35, -0.35 );
\node at ( 13.35, 0.35 ) [above right] {$G, D$};
\end{tikzpicture}}\)
Stanem początkowym jest \(\displaystyle{ d_K}\), stany akceptujące to wierzchołki kwadratowe.
\(\displaystyle{ L = \left\{ G^{n_1} D^{n_2} \ldots G^{n_{2k-1}} D^{n_{2k}} : k \in \NN \cup \{ 0 \} \wedge \bigwedge_{i=1}^{2k} 1 \le n_i \le K \right\}}\)
Stosunkowo łatwo skonstruować automat, który rozpoznaje powyższy język.
\(\displaystyle{ \begin{tikzpicture}
\foreach \i in { 1, 2, 3 }
{
\draw ( 2*\i+1, 2 ) circle [radius=0.5];
\node at ( 2*\i+1, 2 ) {$g_\i$};
\draw [->] ( 2*\i+1.5, 2 ) -- ( 2*\i+2.5, 2 );
\node at ( 2*\i+1.5, 2 ) [above right] {$G$};
\draw ( 2*\i+1, 1.5 ) -- ( 2*\i+1, 0.5 );
\node at ( 2*\i+1, 1.5 ) [below right] {$D$};
}
\node at ( 9, 2 ) {$\ldots$};
\draw [->] ( 9.5, 2 ) -- ( 10.5, 2 );
\node at ( 9.5, 2 ) [above right] {$G$};
\draw ( 11, 2 ) circle [radius=0.5];
\node at ( 11, 2 ) {$g_{K}$};
\draw [->] ( 11.5, 2 ) -- ( 13, 2 ) -- ( 13, 0.5 );
\node at ( 11.5, 2 ) [above right] {$G$};
\draw [->] ( 11, 1.5 ) -- ( 11, 0.5 ) -- ( 1, 0.5 ) -- ( 1, -2 ) -- ( 2.5, -2 );
\node at ( 11, 1.5 ) [below right] {$D$};
\foreach \i in { 1, 2, 3 }
{
\draw ( 2*\i+0.5, -2.5 ) rectangle ( 2*\i+1.5, -1.5);
\node at ( 2*\i+1, -2 ) {$d_\i$};
\draw [->] ( 2*\i+1.5, -2 ) -- ( 2*\i+2.5, -2 );
\node at ( 2*\i+1.5, -2 ) [below right] {$D$};
\draw ( 2*\i+1, -1.5 ) -- ( 2*\i+1, -0.5 );
\node at ( 2*\i+1, -1.5 ) [above right] {$G$};
}
\node at ( 9, -2 ) {$\ldots$};
\draw [->] ( 9.5, -2 ) -- ( 10.5, -2 );
\node at ( 9.5, -2 ) [below right] {$D$};
\draw ( 10.5, -2.5 ) rectangle ( 11.5, -1.5);
\node at ( 11, -2 ) {$d_{K}$};
\draw [->] ( 11.5, -2 ) -- ( 13, -2 ) -- ( 13, -0.5 );
\node at ( 11.5, -2 ) [below right] {$D$};
\draw [->] ( 11, -1.5 ) -- ( 11, -0.5 ) -- ( 1.5, -0.5 ) -- ( 1.5, 2 ) -- ( 2.5, 2 );
\node at ( 11, -1.5 ) [above right] {$G$};
\draw ( 13, 0 ) circle [radius=0.5];
\node at ( 13, 0 ) {$q$};
\draw[->, bend left] ( 13.35, 0.35 ) to [out=45, in=110] ( 14.25, 0 ) to [out=70, in=135] ( 13.35, -0.35 );
\node at ( 13.35, 0.35 ) [above right] {$G, D$};
\end{tikzpicture}}\)
Stanem początkowym jest \(\displaystyle{ d_K}\), stany akceptujące to wierzchołki kwadratowe.