|
Informatyka UJ forum Rocznik 2005 - czyli najlepsze forum w sieci
|
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
|
Wysł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 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
|
Wysł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 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
|
Wysł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 poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
aga
pijak
Dołączył: 25 Wrz 2006
Posty: 114
Przeczytał: 0 tematów
|
Wysł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 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
|
Wysł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 poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
aga
pijak
Dołączył: 25 Wrz 2006
Posty: 114
Przeczytał: 0 tematów
|
Wysł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 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
|
Wysłany: Sob 22:00, 14 Kwi 2007 Temat postu: |
|
|
@aga:
:smt058
|
|
Powrót do góry |
|
|
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
|
Wysł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 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?
|
Wysłany: Sob 23:28, 14 Kwi 2007 Temat postu: |
|
|
Fak, chyba powinienem to ocenzurowac ;) Zanim Aga zobaczy :P
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
aga
pijak
Dołączył: 25 Wrz 2006
Posty: 114
Przeczytał: 0 tematów
|
Wysł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 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
|
Wysłany: Nie 12:04, 15 Kwi 2007 Temat postu: |
|
|
looool xDxDxD
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
jagm
zielony żul
Dołączył: 01 Lut 2006
Posty: 1421
Przeczytał: 0 tematów
|
Wysł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 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
|
Wysł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 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?
|
Wysłany: Nie 12:32, 15 Kwi 2007 Temat postu: |
|
|
a nie bedzie testowych? :)
|
|
Powrót do góry |
|
|
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
|
Wysł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 poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
aga
pijak
Dołączył: 25 Wrz 2006
Posty: 114
Przeczytał: 0 tematów
|
Wysłany: Nie 18:22, 15 Kwi 2007 Temat postu: |
|
|
Jest, już mi jagm przetłumaczył :]
|
|
Powrót do góry |
|
|
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
|
Wysł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 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
|
Wysł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 poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
aga
pijak
Dołączył: 25 Wrz 2006
Posty: 114
Przeczytał: 0 tematów
|
Wysł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 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
|
Wysłany: Nie 22:47, 15 Kwi 2007 Temat postu: |
|
|
hmm... podrzuć podrzuć... będzie strasznie fajnie... :P
|
|
Powrót do góry |
|
|
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?
|
Wysł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 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
|
Wysł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 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
|
Wysł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 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
|
Wysł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 poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
Matjas
pijak
Dołączył: 24 Maj 2006
Posty: 225
Przeczytał: 0 tematów
|
Wysł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:
(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 |
|
|
|
|
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
|