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 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ść
Krisowski
pijak



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

Skąd: z nikąd

PostWysłany: Wto 12:47, 10 Kwi 2007    Temat postu: Kolokwium u dr Foryś

Jakie mogą być zadania na tym kolosie?? Ma ktoś kolokwia z poprzednich lat, było by miło ;) .
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: Czw 23:36, 12 Kwi 2007    Temat postu:

Dlaczego w automacie konkatenacji języków z ostatnich ćwiczeń stan początkowy to (s0, {t0})?
W definicji jest napisane, że stan początkowy takiego automatu to (s0,O) - co to właściwie oznacza? jakie byłoby następne przejście (jakoś nie widzę tutaj możliwości wejścia do drugiego automatu, poza opcją, w której f1(s,a) e T1).

//O - zbior pusty oczywiście ;)

Mam nadzieję, że ktoś zrozumie co tu napisałem i będzie w stanie odpowiedzieć :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: Czw 23:53, 12 Kwi 2007    Temat postu:

s0 akurat w naszym pierwszym automacie było również stanem końcowym, zatem z definicji funkcji przejść należało dodać do zbioru pustego zbiór ze stanem początkowym drugiego automatu ;) .
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: Sob 16:22, 14 Kwi 2007    Temat postu:

Mieliście już to kolokwium? Mam z zeszłego roku, ale jeśli to już nieaktualne, to nie chce mi się na darmo przepisywać ;) (nie mam skanera)
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: Sob 17:16, 14 Kwi 2007    Temat postu:

będziemy mieli dopiero w czwartek... Gdybyś mogła to jakoś dać... było by strasznie fajnie... thx
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: Sob 18:54, 14 Kwi 2007    Temat postu:

No to skoro będzie strasznie fajnie to proszę :)

(1) L = {w e {a,b}* : #a w - #b w = 1 (mod 3)}.
(a) Wykorzystując podany algorytm określ minimalny automat akceptujący język L.
(b) dla otrzymanego automatu określ monoid przejść.
(4 pkt)

(2) Wykorzystując lemat o pompowaniu udowodnij, że język L = {a^n! : n>=0} nie jest językiem regularnym.
(3 pkt)

(3) Niech p e N. Wykaż, że deterministyczny automat akceptujący język L = {a^nb^n : 0<=n<=p} ma co najmniej 2p+2 stany.
(4 pkt)
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: Sob 22:00, 14 Kwi 2007    Temat postu:

@aga:
:smt058
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
chlebek
alkoholik



Dołączył: 04 Lut 2006
Posty: 556
Przeczytał: 0 tematów

Skąd: Siedlce\Kraków

PostWysłany: Sob 22:42, 14 Kwi 2007    Temat postu:

teraz to juz nigdy nam aga zadan nie da ;p
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: Sob 23:28, 14 Kwi 2007    Temat postu:

Fak, chyba powinienem to ocenzurowac ;) Zanim Aga zobaczy :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 11:49, 15 Kwi 2007    Temat postu:

No tak, a Makros obiecywał, że będzie strasznie fajnie :P
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Yoter
zielony żul



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

Skąd: Gościeradów

PostWysłany: Nie 12:04, 15 Kwi 2007    Temat postu:

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



Dołączył: 01 Lut 2006
Posty: 1421
Przeczytał: 0 tematów


PostWysłany: Nie 12:07, 15 Kwi 2007    Temat postu:

aga napisał:
No tak, a Makros obiecywał, że będzie strasznie fajnie :P

bo to "strasznie fajnie" było ze wskazaniem na "strasznie" ;]
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
oinopion
żul



Dołączył: 28 Lis 2005
Posty: 858
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Nie 12:14, 15 Kwi 2007    Temat postu:

Ej, proste... Przynajmniej jak się chodziło na ćwiczenia. Robiliśmy te zadania.
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: Nie 12:32, 15 Kwi 2007    Temat postu:

a nie bedzie testowych? :)
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 14:49, 15 Kwi 2007    Temat postu:

@kg86:
Na ćw z dyskretnej nie było testowych, zatem nie spodziewałbym się takich rewelacji ;) .

aga napisał:
No tak, a Makros obiecywał, że będzie strasznie fajnie :P

A nie jest? :D
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 18:22, 15 Kwi 2007    Temat postu:

Jest, już mi jagm przetłumaczył :]
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: Nie 20:56, 15 Kwi 2007    Temat postu:

Czy mógłby ktoś zamieścić rozwiązania tych zadań :) ?
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: Nie 21:13, 15 Kwi 2007    Temat postu:

popieram :) dla mnie takie trywialne te zadanka nie sa niestety...
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 22:03, 15 Kwi 2007    Temat postu:

Znalazłam moje rozwiązania zadań i mogłabym je komuś podrzucić, ale aż strach proponować :P
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: Nie 22:47, 15 Kwi 2007    Temat postu:

hmm... podrzuć podrzuć... będzie strasznie fajnie... :P
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: Pon 0:31, 16 Kwi 2007    Temat postu:

Makros, perwresie :P

To mozemy sie tak umowic ze bede od teraz wywalal wszystkie posty Spectera z tego topicu, to moze sie Aga zgodzi ;)
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: Wto 16:54, 17 Kwi 2007    Temat postu:

Witam sertechnie wshystkih polakuf!
Saluto Alcoholico!

Siedzimy se właśnie z fenem i kapuhem nad TJA i nasuwają się nam takie pytanka:
1. WTF?!
2. Jak się minimalizuje automaty za pomocą stabilizujących się ciągów relacji?
( "to co się te ro rozbija ;p" - kapuh )

Z góry dzięki za odpowiedź.
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: Wto 18:56, 17 Kwi 2007    Temat postu:

@Zenek:
O ile dobrze pamięcią sięgam, to przecież odpowiadałeś z tego przy tablicy :shock: .

Ech, reguła jest taka, że dodajesz każdą literkę alfabetu do każdego słowa w danej klasie równoważności i patrzysz, czy wszystkie te słowa po dodaniu tych literek zawsze przechodzą do tych samych klas. Jeżeli nie, to klasa ulega rozbiciu. I tak w kółko, aż nie da się niczego rozbić. Tyle ile klas nam wyjdzie na końcu, tyle będziemy mieli stanów.

Przykład z ćwiczeń:
Masz język L = A*abA* , gdzie A = {a, b}.
Bazowe klasy równoważności to: p1 = L , A* - L (= b*a*)
Dla pierwszej klasy, niezależnie jaką literkę dodamy, dalej każde słowo będzie dalej w tej klasie.
Dla drugiej klasy jak dodamy 'a' na końcu, to nic się nie zmieni (dalej elementy nie są w klasie pierwszej). Ale teraz, jeżeli dodamy 'b' na końcu, to zajdą 2 przypadki:
1) dla b*a+ słowo będzie należało do pierwszej kl. równ.;
2) dla b* słowo będzie należało do drugiej kl. równ.
Zatem ta relacja ulega rozbiciu. Mamy zatem w drugim kroku taki ciąg klas równoważności:
p2 = L, b*, b*a+
Sprawdzamy analogicznie jak w poprzednim kroku i wychodzi nam, że relacja p3 jest równa p2.

Mamy zatem 3 stany. Stanami końcowymi są te klasy, które po zsumowaniu tworzą nam słowa języka L (w tym wypadku jedna klasa). Stanem początkowym jest ten stan, który zawiera słowo puste - czyli u nas b*.

Konstruujemy krawędzie w grafie (x.alfa = y oznacza, że ze stanu x po dodaniu literki alfa przechodzimy w stan y):
b*.a = b*a+
b*.b = b*
b*a+.a = b*a+
b*a+.b = L
L.a = L
L.b = L
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: Wto 19:04, 17 Kwi 2007    Temat postu:

Spectro napisał:
@Zenek:
O ile dobrze pamięcią sięgam, to przecież odpowiadałeś z tego przy tablicy :shock: .

To nic nie implikuje ;)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Matjas
pijak



Dołączył: 24 Maj 2006
Posty: 225
Przeczytał: 0 tematów


PostWysłany: Wto 20:41, 17 Kwi 2007    Temat postu:

To ja mam takie pytanka - może trochę czepialskie i dziwne, ale:

1) Czy w prawach gramatyki moze się pojawić na przykład coś takiego:
Kod:
va -> b

(a, b - terminale, v - nieterminal)
Znaczy się: moja intuicja podpowiada, że nie bardzo, ale czy to jest sprzeczne z definicją z książki (2.0.5)?

2) Czy wiemy, ile elementów ma monoid przejść dla danego automatu? Czy ma to jakiś związek z liczbą stanów, albo czym kolwiek innym?

3) Jak się minimalizuje automat w oparciu o tabelkę? No wiecie, tą taką śmieszną z krzyżykami.[/code]
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 1, 2, 3  Następny
Strona 1 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