Problem z windą i językiem regularnym

Zdania. Tautologie. Język matematyki. Wszelkie zagadnienia związane z logiką matematyczną...
Siergiej29
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 11 wrz 2014, o 12:59
Płeć: Mężczyzna
Lokalizacja: Opole

Problem z windą i językiem regularnym

Post autor: Siergiej29 » 11 wrz 2014, o 13:21

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
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Siergiej29
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 11 wrz 2014, o 12:59
Płeć: Mężczyzna
Lokalizacja: Opole

Problem z windą i językiem regularnym

Post autor: Siergiej29 » 23 wrz 2014, o 13:49

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.

Lala123
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 28 kwie 2019, o 12:07
Płeć: Mężczyzna
Lokalizacja: Rzeszow

Re: Problem z windą i językiem regularnym

Post autor: Lala123 » 28 kwie 2019, o 12:08

Kurde,ma ktoś może ten obrazek DFA? potrzebuję żeby zaliczyć przedmiot!!! ważne

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 9017
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 1943 razy

Re: Problem z windą i językiem regularnym

Post autor: Dasio11 » 28 kwie 2019, o 17:53

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.

Lala123
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 28 kwie 2019, o 12:07
Płeć: Mężczyzna
Lokalizacja: Rzeszow

Re: Problem z windą i językiem regularnym

Post autor: Lala123 » 30 kwie 2019, o 07:47

Dzięki za pomoc!

ODPOWIEDZ