http://ii.drx.pl/ 2026-05-23T20:02:59+02:00 http://ii.drx.pl/ http://ii.drx.pl/lib/images/favicon.ico text/html 2011-02-22T23:58:36+02:00 http://ii.drx.pl/jezyki_formalne_i_zlozonosc_obliczeniowa:lista1?rev=1298415516&do=diff JFiZO - Zadanie 09.001 Z dedykacją dla driksa, chociaż jest pałkossaczem. Załóżmy sobie nie wprost, że istnieje automat , o , rozpoznający . Weźmy ,, takie, że . (Jak się robi deltę z daszkiem? Na bazy się spieszę, nie mam czasu googlać.) Takie i istnieją, bo każde słowo zwraca jakiś stan, a stanów jest mniej niż słów -znakowych. text/html 2011-05-12T20:31:25+02:00 http://ii.drx.pl/jezyki_formalne_i_zlozonosc_obliczeniowa:lista10?rev=1305225085&do=diff JFIZO - Zadanie 09.085 Jeśli , to istnieje NTM . Maszyna niedeterministyczna podczas obliczenia korzysta z niedeterminizmu wtedy, gdy ma więcej niż jedną możliwą akcję, dla jednej konfiguracji. Możemy zmodyfikować maszynę, aby najpierw wyznaczała sobie na taśmie pewien obszar, zapisała na nim tyle liczb, ile ma niedeterministycznych wyborów w obliczeniu. Potem przechodzimy do normalnego obliczenia. W momencie natrafienia na niejednoznaczną konfigurację, czytamy pierwszą z wylosowanych liczb … text/html 2011-05-12T20:32:01+02:00 http://ii.drx.pl/jezyki_formalne_i_zlozonosc_obliczeniowa:lista11?rev=1305225121&do=diff JFiZO - Zadanie 09.100 * [Rozwiązania niektórych zadań Arkadiusza Janickiego] JFiZO - Zadanie 09.102 * [Rozwiązania niektórych zadań Arkadiusza Janickiego] <- Bierzemy instancję i konstruujemy instancję Jeśli x = y -> trywialne text/html 2011-05-23T13:01:14+02:00 http://ii.drx.pl/jezyki_formalne_i_zlozonosc_obliczeniowa:lista12?rev=1306148474&do=diff JFiZO - Zadanie 09.121 Musimy udowodnic, ze . Regexp mozemy reprezentowac w postaci NFA w liniowej pamieci (Lemma 1.29, example 1.30, example 1.31, Sipser). TODO JFiZO - Zadanie 09.123 Zdefiniujmy sobie 3-arnego XOR'a tak: Teraz używamy po prostu algorytmu z zadania 126, z tym, że XOR'a 2-arnego zastępujemy 3-arnym. text/html 2011-05-23T13:02:19+02:00 http://ii.drx.pl/jezyki_formalne_i_zlozonosc_obliczeniowa:lista13?rev=1306148539&do=diff text/html 2011-05-23T13:03:08+02:00 http://ii.drx.pl/jezyki_formalne_i_zlozonosc_obliczeniowa:lista14?rev=1306148588&do=diff JFiZO - Zadanie 09.105 * [Rozwiązania niektórych zadań Arkadiusza Janickiego] JFiZO - Zadanie 09.109 Graf ma mieć taką własność, że dla każdego wierzchołka może on sąsiadować z conajwyzej jednym wierzchołkiem o takim samym kolorze. text/html 2011-05-23T13:04:23+02:00 http://ii.drx.pl/jezyki_formalne_i_zlozonosc_obliczeniowa:lista15?rev=1306148663&do=diff text/html 2011-03-06T11:11:09+02:00 http://ii.drx.pl/jezyki_formalne_i_zlozonosc_obliczeniowa:lista2?rev=1299406269&do=diff JFiZO - Zadanie 09.011 [Automat do zadania] * Regexp1 (błędny): * Regexp2: Duży nawias to wszystkie możliwe przejścia ze stanu początkowego ponownie na stan początkowy. Następnie są wszystkie możliwe zakończenia na stanach akceptujących. text/html 2011-03-13T18:20:08+02:00 http://ii.drx.pl/jezyki_formalne_i_zlozonosc_obliczeniowa:lista3?rev=1300036808&do=diff 1. Czy istnieje takie wyrażenie regularne , że ? Nie. Załóżmy nie wprost, że istnieje. Rozważmy . Wtedy niewątpliwie . A więc zaczyna się od i kończy na . Mamy: dla pewnego i dodatkowo (usuwamy końcowe z wyrazu będącego w ) oraz (usuwamy początkowe z wyrazu w ). text/html 2011-03-16T15:41:11+02:00 http://ii.drx.pl/jezyki_formalne_i_zlozonosc_obliczeniowa:lista4?rev=1300286471&do=diff JFiZO - Zadanie 09.028 * * * S S0S1S | S1S0S | S0S1S1S | S1S0S1S | S1S1S0S | * TODO Tutaj chyba można olać leading --- Alistra 2010/03/21 15:37 : Zawsze dokładamy nic, zero i jeden, dwa zera i jeden. Co zapewnia nam warunek: text/html 2011-03-22T21:11:38+02:00 http://ii.drx.pl/jezyki_formalne_i_zlozonosc_obliczeniowa:lista5?rev=1300824698&do=diff JFiZO - Zadanie 11.006 Pokazać, że jeśli jest regularny, to też jest. Niech będzie DFA takim, że, . Skonstruujemy sobie NFA B rozpoznający . - oznacza to trójki złożone ze stanu A, ze stanu odwróconego A (podzbioru ) i jednej flagi. Odwrócony A to NFA powstały przez odwrócenie strzałek (funkcja przejścia staje się relacją). Flagę będziemy czytać jako „czy przekroczyłeś już granicę ”. text/html 2011-04-10T18:50:54+02:00 http://ii.drx.pl/jezyki_formalne_i_zlozonosc_obliczeniowa:lista6?rev=1302454254&do=diff JFIZO - Zadanie 09.049 [Mało zadeptany śnieg - drak] (zad 47) func: * niemalejąca: * całkowita: * rekurencyjna: , Przypadek 1: func - od pewnego momentu stała int g(n) { for(i = 0; func(i) <= max; i++) { if (func(i) == n) return 1; if (func(i) == max) return 0; } } text/html 2011-04-10T18:52:03+02:00 http://ii.drx.pl/jezyki_formalne_i_zlozonosc_obliczeniowa:lista7?rev=1302454323&do=diff JFIZO - Zadanie 09.060 [Mało zadeptany śnieg - drak (59)] JFIZO - Zadanie 09.061 [Mało zadeptany śnieg - drak (60)] JFIZO - Zadanie 09.063 [Mało zadeptany śnieg - drak (62)] JFIZO - Zadanie 09.068 [Mało zadeptany śnieg - drak (66)] text/html 2011-04-20T13:51:09+02:00 http://ii.drx.pl/jezyki_formalne_i_zlozonosc_obliczeniowa:lista8?rev=1303300269&do=diff JFIZO - Zadanie 09.073 [Mało zadeptany śnieg - drak (69)] JFIZO - Zadanie 09.078 [Mało zadeptany śnieg - drak] JFIZO - Zadanie 09.079 [Mało zadeptany śnieg - drak] JFIZO - Zadanie 09.081 [Mało zadeptany śnieg - drak] text/html 2011-04-26T19:41:45+02:00 http://ii.drx.pl/jezyki_formalne_i_zlozonosc_obliczeniowa:lista9?rev=1303839705&do=diff JFIZO - Zadanie 09.088 Każdą klauzę z zamieniamy osobno. Mamy . Dodajemy dwie nowe zmienne logiczne i . Z tworzymy . Dowód. Załóżmy, że istnieje wartościowanie, które spełnia tę formułę . Każda klauzula musi zostać spełniona, zatem w każdej klauzuli istnieje co najmniej jeden literał, który jest spełniony przez to wartościowanie. W takim wypadku ustawiamy odpowienio wartościowania i .