szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna
PostNapisane: 11 wrz 2014, o 13:21 
Użytkownik

Posty: 2
Lokalizacja: Opole
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ętroj (i \neq j) uważamy za jednostkową akcję. Z każdą taką akcją wiążemy literę: G jeśli i < j, D jeśli 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 {G, D}. Niech 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
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna
PostNapisane: 23 wrz 2014, o 13:49 
Użytkownik

Posty: 2
Lokalizacja: Opole
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 G i D z którego ma się składać język. G i D są to przejścia ze stanu A do stanu B.
Przejazd windy bez zatrzymania z piętra i na piętroj (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 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 D.
Zaczynamy przejazd z parteru i kończymy na parterze. Jak juz pewnie wiadomo pierwszą literą słowa będzie G bo zaczynając z parteru możemy jechać tylko w górę. Ostatnim słowem będzie D.
Np: zaczynamy z parteru i jedziemy najpierw na piętro 5, potem na 12, następnie na 6 i na ostatnie k, powrotem na parter. Powstanie nam słowo GGDGD
Całe zdanie można sobie wyobrazić jako ciąg znaków + i -
Za każdym znakiem musisz wpisać liczbę ale tak żeby cale wyrażenie było równe 0
Ograniczeniem jest to że za każdym znakiem musi stać liczba przedziału <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.

Obrazek

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.
Góra
Mężczyzna
PostNapisane: 28 kwi 2019, o 12:08 
Użytkownik

Posty: 2
Lokalizacja: Rzeszow
Kurde,ma ktoś może ten obrazek DFA? potrzebuję żeby zaliczyć przedmiot!!! ważne
Góra
Mężczyzna
PostNapisane: 28 kwi 2019, o 17:53 
Moderator
Avatar użytkownika

Posty: 8381
Lokalizacja: Wrocław
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ż K i każdy spójny podciąg złożony z liter D ma długość nie większą niż K. Symbolicznie:

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.

\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 d_K, stany akceptujące to wierzchołki kwadratowe.
Góra
Mężczyzna
PostNapisane: 30 kwi 2019, o 07:47 
Użytkownik

Posty: 2
Lokalizacja: Rzeszow
Dzięki za pomoc! :)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Problem z implikacja  Aram  6
 Problem z przekształceniem do postaci zanegowanej sumy  szturm  5
 Problem z prawem rozdzielności.  ikacper  4
 Algebra Boola - problem  pkwiatkowski  0
 f zdaniowa problem  lightinside  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl