Co bylo na cwiczeniach ?

6. 10. 2004.
Zadania z pierwszej serii zbiorku, str. 1-2.
Zadanie o barmanie (4 lub 3 szklanki).
Charakteryzacja jezyka nawiasowego.
Synchronizacja. Przyklad opisany w rozdziale 2.7 pierwszego odcinka zbiorku
(Algorytmy i zlozonosc), zadanie 11 (str. 10).
Jak sprawdzic, ze zbior slow jest kodem -- oszacowanie dlugosci kontrprzykladu.

Problemy do pomyslenia:
Barman -- 5 szklanek (n szklanek).
Dlaczego w przykladzie na synchronizacje (n-1)^2 jest najkrotsza mozliwa
dlugoscia slowa synchronizujacego.
Rozpoznawanie kodow -- algorytm.
Dwa slowa {x,y} zawsze tworza kod, chyba ze xy = yx.

13.10.2006.
Zadanie o barmanie - czesciowo rozwiazane. (Dla n nieparzystego barman przegrywa.)
Wyrazenia regularne opisujace jezyki w rodzaju
--- slowa bez 000,
--- parzysta liczba jedynek i zer.
Automat skonczony badajacy liczby wystapien poszczegolnych symboli modulo stale.
Automat skonczony badajacy podzielnosc przez 7 liczb w systemie dziesietnym (lub ogolnie).

Problemy do pomyslenia:
Jak wyzej, ale liczby pisane wspak.
Nad jednoliterowym alfabetem jezyk postaci L^* jest zawsze regularny.

20.10.2006.
Konstrukcja automatu rozpoznajacego podzielnosc -- przy obu kierunkach zapisu.
Uwaga ogolna: lustrzane odbicie jezyka regularnego jest regularne.
Konstrukcja automatu rozpoznajacego dodawanie pisemne.
Lemat Ardena: Jesli A i B sa jezykami, to rozwiazaniem rownania X = AX + B jest A*B.
Jesli A nie zawiera slowa pustego, jest to rozwiazanie jedyne.
Konstrukcja wyrazenia regularnego na podstawie automatu --- metoda rozwiazywania rownan.

Problemy do pomyslenia:
Dowodzenie nieregularnosci. Przyklady z zadania 2.2.1.
Jezyk reprezentacji ulamkow binarnych mniejszych niz liczba rzeczywista r jest regularny wtt gdy r jest wymierne (Zadanie 2.3.5).

27.10.2006.
Dowodzenie nieregularnosci (a^m b^n, gdzie m i n wzglednie pierwsze).
Konstrukcja automatu deterministycznego rozpoznajacego wszystkie slowa t (teksty), w ktorych wystepuje ustalone podslowo w (wzorzec). Liczba stanow: n+1 (gdzie n = |w|).
Uwaga: Nietrywialnych strzalek wstecznych (tzn. nie prowadzacych do 0) jest co najwyzej n (bo kazda z nich musi przesuwac o inny dystans).

Konstrukcja automatu deterministycznego rozpoznajacego wszystkie podslowa slowa w. Liczba stanow: 2n.

Problem do pomyslenia:
Konstrukcja automatu deterministycznego rozpoznajacego wszystkie teksty, w ktorych wystepuje jedno z ustalonego skonczonego zbioru slow: w_1,...,w_k.

3.11.2006.
Konstrukcja automatu dla wielu wzorcow. Stany tworzy drzewo podslow tych wzorcow.
Nad jednoliterowym alfabetem kazdy jezyk postaci L* jest regularny. Metoda: jesli L zawiera slowo dlugosci k > 0, dzielimy wszystkie slowa ze wzgledu na dlugosc modulo k.
Konstrukcja automatu rozpoznajacego Cycle (L) = { y x : x y nalezy do L }, jezeli znamy automat dla L.

Problem do pomyslenia:
Jesli L jest regularny, to rowniez jezyk {w : w w nalezy do L } jest regularny.
Wiele podobnych zadan w pierwszej serii zbiorku, 2.3.6-8, str. 5.

10.11.2006.
Rozwiazanie powyzszego zadania i podobnych: jesli L jest regularny, to regularne sa rowniez jezyki
0.5 L = {w : istnieje v, ze |v|=|w| i wv nalezy do L },
log L = {w : istnieje v, ze |v|= 2^|w| i wv nalezy do L }.

Konstrukcja automatow minimalnych dla konkretnych zadan: zadanie o windzie, zadanie o akcjach (zob. zbiorek 2.4, str. 6).
Minimalizacja zadanego automatu (podzielnosc liczb binarnych przez 6) metoda "sklejania" stanow.
Uwaga: stanow p i q nie mozna skleic, gdy automat akceptuje pewne slowo v ze stanu p i nie akceptuje go ze stanu q (lub vice-versa).

17.11.2006.
Dla danych automatow deterministycznych A i B o m i n stanach odpowiednio, najkrotsze slowo w czesci wspolnej jezykow L(A) i L(B) ma dlugosc nie wieksza niz mn.
Dla danego automatu niedetrministycznego, najkrotsze slowo, ktorego on nie akceptuje moze miec dlugosc wykladnicza wzgledem liczby stanow.
Przyklad: Ustalmy n. Rozwazmy slowo W_n = c_0 $ c_1 $ ... $ c_{2^n}, gdzie c_0, c_1, ..., c_{2^n}, sa wszystkimi slowami dlugosci n nad alfabetem {0,1}. Mozna skonstruowac automat niedeterministyczny rozpoznajacy wszystkie slowa z wyjatkiem W_n, o liczbie stanow liniowej wzgledem n.

Problem do pomyslenia:
Dla danych automatow deterministycznych A i B oszacowac dlugosc najkrotszego slowa w roznicy symetrycznej L(A) i L(B).