Forum Informatyka UJ forum Strona Główna Informatyka UJ forum
Rocznik 2005 - czyli najlepsze forum w sieci
 
 FAQFAQ   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy   GalerieGalerie   RejestracjaRejestracja 
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

Kolokwium u dr Foryś
Idź do strony Poprzedni  1, 2, 3  Następny
 
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 2 rok / 4 semestr - Teoria języków i automatów
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
aga
pijak



Dołączył: 25 Wrz 2006
Posty: 114
Przeczytał: 0 tematów


PostWysłany: Wto 21:09, 17 Kwi 2007    Temat postu:

Ryzykuję, jakby ktoś chciał moje kolokwium, to będę je miała jutro ze sobą.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
ZenonZajebich
żul



Dołączył: 19 Lis 2005
Posty: 662
Przeczytał: 0 tematów

Skąd: BRAK DANYCH

PostWysłany: Śro 15:45, 18 Kwi 2007    Temat postu:

fen :
czy ktoś może rozwiązać zadanko:
znajdź automat minimalny dla języka L = (a+b)a((a+b)^2)*
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Krisowski
pijak



Dołączył: 05 Mar 2006
Posty: 218
Przeczytał: 0 tematów

Skąd: z nikąd

PostWysłany: Śro 16:11, 18 Kwi 2007    Temat postu:

L = (a+b)a((a+b)^2)*
Konstrukcja automatu minimalnego:

Kod:

p1: L, A*\L = (a+b)bA* + (a+b)a((a+b)^2)*(a+b) + a + b + 1
p2: L, (a+b)bA* + 1, (a+b)a((a+b)^2)*(a+b), (a+b)
p3: L, (a+b)bA*, (a+b), 1, (a+b)a((a+b)^2)*(a+b)
    s2     s4      s1   s0             s3


   s0   s1   s2   s3   s4
a  s1   s2   s3   s2   s4
b  s1   s4   s3   s2   s4

s0 - stan początkowy
s2 - stan końcowy
Jak się pomyliłem to niech mnie ktoś poprawi, ale tak chyba było na ćwiczeniach, więc powinno być dobrze.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Crow
alkoholik



Dołączył: 14 Mar 2006
Posty: 497
Przeczytał: 0 tematów

Skąd: KRK-NH

PostWysłany: Śro 16:56, 18 Kwi 2007    Temat postu:

Moim zdaniem tutaj (i na cwiczeniach byl blad):

wezmy dwa slowa z klasy: (a+b)a((a+b)^2)*(a+b)
dokladniej:
(a+b)a((a+b)^2)*a i (a+b)a((a+b)^2)*b

Jesli do obu dodamy a to pierwsze trafi do jezyka a drugie.... no wlasnie gdzie? IMHO brakuje tutaj jeszcze jednej klasy do ktorej trafiloby to drugie slowo. Zreszta... jesli narysujesz sobie graf na podstawie tych 5 stanow z cwiczen a nastepnie sprawdzisz dla dowolnego slowa z jezyka to latwo zauwazyc ze cos jest jednak nietak.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Krisowski
pijak



Dołączył: 05 Mar 2006
Posty: 218
Przeczytał: 0 tematów

Skąd: z nikąd

PostWysłany: Śro 17:05, 18 Kwi 2007    Temat postu:

Też się kiedyś nad tym zastanawiałem. Doszedłem do wniosku, że chodzi tu o interpretację (a+b)^2 .
Jeśli zinterpretujesz to jako dowolne słowo o długości dwa {aa, ab, ba, bb} to rozwiązanie z ćwiczeń (i moje) jest poprawne, bo jak weźmiesz te dwa słowa:
(a+b)a((a+b)^2)*a i (a+b)a((a+b)^2)*b
to cokolwiek byś nie dopisał będzie miało znów parzystą długość.

Znów nie wiem, czy mam rację, ale przyjmuję, że dr Foryś nie pomyliła się na ćwiczeniach i tak to sobie tłumaczę ;) .
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Crow
alkoholik



Dołączył: 14 Mar 2006
Posty: 497
Przeczytał: 0 tematów

Skąd: KRK-NH

PostWysłany: Śro 17:11, 18 Kwi 2007    Temat postu:

hmm... mnie sie wydaje ze:

(a+b)^2 = (aa | bb)

EDIT:

chociaz chyba masz racje... ale prosilbym kogos o potwierdzenie

EDIT2:

Potwierdzam... mam w zeszycie zapisane ze: ((a+b)^2)* = (ab + ba + bb + aa)*

:P
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kg86
zielony żul



Dołączył: 22 Gru 2005
Posty: 1194
Przeczytał: 0 tematów

Skąd: pochodze?

PostWysłany: Śro 21:34, 18 Kwi 2007    Temat postu:

a propo minimalizacji automatow :) moglby ktos wytlumaczyc tak na chlopski rozum na czym polega konstrukcja automatu minimalnego z jakiegos innego automatu? :) tzn. w jaki sposob trzeba rozdzielac na grupy te stany? ktore beda poczatkowe, ktore koncowe i kiedy trzeba przestac je rozdzielac? :)
btw. nie pytam o ta metoda z trojkatna tabelka, tylko o metode ze zwykla tabelka stanow ;)

EDIT: ok, juz nie trzeba, sam skumalem :P
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
aga
pijak



Dołączył: 25 Wrz 2006
Posty: 114
Przeczytał: 0 tematów


PostWysłany: Nie 17:30, 03 Cze 2007    Temat postu:

Podobno nadchodzi kolokwium, więc...

Kolokwium 2 (2006)

(1) Wykorzystując lemat o pompowaniu udowodnij że język L = {w(odbicie zwierciadlane(w))w : w e {a,b}*} nie jest językiem bezkontekstowym (3 pkt)

(2) Określ automat ze stosem akceptujący język L = {a^nb^ma^pb^q : n=m lub p=q, n,m,p,q>=1}
(a) Czy język L jest językiem deterministycznym? (4 pkt)
(b) * Czy język L jest językiem jednoznacznym? (2 pkt)
(c) * Określ najmniejsze k takie że język L e L k lin (2 pkt)

(3) Rozwiązując stowarzyszony układ równań określ wyrażenie regularne reprezentujące język L(G), gdzie G = ({v0,v1,v2},{a,b},v0,P)
P = {v0->av1, v0->bv2, v0->1, v1->bv0, v1->av2, v2->av0,v2->bv1} (2 pkt)

@Spectro: tylko nie dziękuj:P
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Nie 17:35, 03 Cze 2007    Temat postu:

aga napisał:
@Spectro: tylko nie dziękuj:P

:(
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
ZenonZajebich
żul



Dołączył: 19 Lis 2005
Posty: 662
Przeczytał: 0 tematów

Skąd: BRAK DANYCH

PostWysłany: Nie 19:26, 03 Cze 2007    Temat postu:

Wie ktoś moze o co chodziło w zadaniu z ostatnich ćwiczeń które robił makros?
Bo siedzimy z kapuhem, próbujemy rozkminić to dziadostwo i ni hu hu...
Chodzi o to takie z trójkami...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Makros
pijak



Dołączył: 01 Gru 2005
Posty: 420
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Pon 22:04, 04 Cze 2007    Temat postu:

dobra.. apropo trzeciego od Agi...:
To mi wyszło tak:

v0 = [ (a+b^2) (ab)* (b+a^2)]* + 1

Tylko mi nie mówić, że źle mam... bo taki ładny wynik... :P
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Fen
zielony żul



Dołączył: 22 Lut 2006
Posty: 946
Przeczytał: 0 tematów

Skąd: Bochnia

PostWysłany: Pon 22:19, 04 Cze 2007    Temat postu:

jak dojdę do tego tematu to Ci odpowiem ;p
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Pon 22:20, 04 Cze 2007    Temat postu:

@Makros:
Źle masz :P . A przynajmniej ja nie widzę, jak można z tej postaci uzyskać słowo "ba", które łatwo otrzymać przez v0 -> bv2 -> bav0 -> ba .

Mi wyszło: (aa*b + ba + bba*b)*
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Makros
pijak



Dołączył: 01 Gru 2005
Posty: 420
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Pon 22:25, 04 Cze 2007    Temat postu:

bo głupi jestem i się pomyliłem przy przepisywaniu do linijki niżej.. :P

mam tak:

v0 = [ (a+b^2) (ab)* (b+a^2) + ba]*

kurcze... chyba to policzę jeszcze raz...

edit:

a z Twojego można niby zrobić: bbab :P albo aab :p


Ostatnio zmieniony przez Makros dnia Pon 22:33, 04 Cze 2007, w całości zmieniany 1 raz
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Pon 22:32, 04 Cze 2007    Temat postu:

A z Twojego "bbaa" :lol: .

edit:
Oczywiście, że tamte słowa da się zrobić. Chyba, że widzę inne produkcje :p .

edit2:
Faktycznie widzę inne produkcje :x . Robię to jeszcze raz.


Ostatnio zmieniony przez Spectro dnia Pon 22:37, 04 Cze 2007, w całości zmieniany 1 raz
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Makros
pijak



Dołączył: 01 Gru 2005
Posty: 420
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Pon 22:36, 04 Cze 2007    Temat postu:

Spectro napisał:
A z Twojego "bbaa" :lol: .

edit:
Oczywiście, że tamte słowa da się zrobić. Chyba, że widzę inne produkcje :p .


bbaa:

v0 -> bv2 -> bbv1 -> bbav2 -> bbaav0 -> bbaa ... wiec o so chozi... ?

Spectro napisał:
edit2:
Faktycznie widzę inne produkcje Mad . Robię to jeszcze raz.


ok... :)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Pon 23:34, 04 Cze 2007    Temat postu:

Ostatecznie, przy już właściwych produkcjach, wyszło mi to samo... Ale to trochę trwało, zanim wymyśliłem najprostszą formę wyliczeń (wyznaczamy kolejno: v1(v0), v2(v0) i ostatecznie v0).
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Makros
pijak



Dołączył: 01 Gru 2005
Posty: 420
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Wto 9:55, 05 Cze 2007    Temat postu:

ad 2. czy ten język akceptuje a^n b^m a^p b^q n=m i p=q... ? w sumie tam jest napisane "lub" a nie "albo"... wiec... ?

edit:

nikt nie wie... ?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Crow
alkoholik



Dołączył: 14 Mar 2006
Posty: 497
Przeczytał: 0 tematów

Skąd: KRK-NH

PostWysłany: Wto 15:25, 05 Cze 2007    Temat postu:

a maszyna Turinga bedzie?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Makros
pijak



Dołączył: 01 Gru 2005
Posty: 420
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Wto 17:47, 05 Cze 2007    Temat postu:

Ze tak powiem... Dobre pytanie...

Wie ktoś... ?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Wto 17:58, 05 Cze 2007    Temat postu:

Maszyna Turinga jest absolutem - ona jest wszedzie :D
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kg86
zielony żul



Dołączył: 22 Gru 2005
Posty: 1194
Przeczytał: 0 tematów

Skąd: pochodze?

PostWysłany: Wto 23:14, 05 Cze 2007    Temat postu:

maszyna turinga z tego co pamietam moze sie pojawic :P
ale to jest proste :) WDI nie pamietacie? :P
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Fen
zielony żul



Dołączył: 22 Lut 2006
Posty: 946
Przeczytał: 0 tematów

Skąd: Bochnia

PostWysłany: Wto 23:53, 05 Cze 2007    Temat postu:

w sumie lepsza maszynka Turinga niż jakiś dowodzik :D
a z tego co pamiętam na WDI (u dr Kawy) to robiliśmy bardziej zaawansowane maszyny niż te co na ostatnich ćwiczeniach z Marysia :)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kg86
zielony żul



Dołączył: 22 Gru 2005
Posty: 1194
Przeczytał: 0 tematów

Skąd: pochodze?

PostWysłany: Śro 1:50, 06 Cze 2007    Temat postu:

moglby ktos (kto jeszcze nie spi) wyjasnic mi roznice miedzy automatem, ktory akceptuje jezyk przez stany koncowe, oraz przez pusty stos? :)
EDIT: nie trzeba :) znalazlem przyklady :) ech... brac sie o 23 za TJA, to jednak bylo troche za pozno :P
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Fen
zielony żul



Dołączył: 22 Lut 2006
Posty: 946
Przeczytał: 0 tematów

Skąd: Bochnia

PostWysłany: Śro 15:54, 06 Cze 2007    Temat postu:

no sam nie wiem jak to będzie... może się uda zdobyć koło 6pk, więc może jakimś cudem zalkę dostanę...
jak zwykle głupie błędy plus dość trudne jedno zadanie...

oby Maria byłą dla nas łaskawa...
Powrót do góry
Zobacz profil autora
Wyświetl posty z ostatnich:   
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 2 rok / 4 semestr - Teoria języków i automatów Wszystkie czasy w strefie EET (Europa)
Idź do strony Poprzedni  1, 2, 3  Następny
Strona 2 z 3

 
Skocz do:  
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach

fora.pl - załóż własne forum dyskusyjne za darmo
Powered by phpBB © 2001, 2005 phpBB Group
Regulamin