JAO 2011: co bylo na wykladzie



18. 2. 2011
Nieformalna dyskusja tego co bedzie na wykladach.
Podstawowe operacje na slowach i jezykach formalnych.
Definicja jezykow regularnych.
Definicja wyrazen regularnych.
Definicja deterministycznych i niedeterministycznych automatow skonczonych.
25.02 2011
Analiza automatu: automaty na wyrazenia regularne
Synteza automatu: wyrazenia regularne na automaty
Dolne oszacowanie na (wykladnicza) wielkosc wyrazenia.
patrz opis rozwiazania , opis problemu (zadanie 5)
4. 03. 2011
Lemat o pompowaniu. Kilka przykladow dowodzenia nieregularnosci
determinizacja automatow niedeterministycznych.
szacowanie liczby stanow przez ilorazy
dowod tego ze determinizacja moze dac wykladniczy wzrost automatu
Lemat Higmana (dowod jest tutaj)
zastosowanie do dowodzenia regularnosci dla subsekwencji i supersekwencji dowolnego jezyka
Automaty niedeterministyczne z pustymi przejsciami.
11. 03. 2011
Automat dla odwroconego jezyka L^R.
Abstrakcyjny algorytm Brzozowskiego minimalizacji.
Konstrukcja automatu dla problemu "string-matching" -jeden wzorzec.
Dowod ze automat ma co najwyzej 2n tranzycji po optymalizacji.
Konstrukcja automatu dla problemu "string-matching" -wiele wzorcow.
18. 03. 2011
Automat skonczony dla zbioru wszystkich sufiksow jednego slowa.
Dowody: liczba stanow <= 2n, liczba tranzycji <= 3n.
Algorytm na rownowaznosc w czasie prawie liniowym, n log^*n.
Minimalizacja automatu, czas kwadratowy, pamiec liniowa.
Problemy decyzyjne dla automatow: pustosc, nieskonczonosc jezyka itp.
25. 03. 2011
Automaty skonczone z wyjsciem: Mealy'ego i Moore'a
Jesli dwa stany nierownowazne w aut. det. to rozroznialne dla
slow o dlugosci linoiowej
dla niedeterministycznych automatow moze byc dlugosci dopiero wykladniczej
Automaty skonczone dwukierunkowe.
Gramatyki bezkontekstowe, przyklady
Lemat ''o pompowaniu'' dla jez. bezkontekstowych.
Zastosowania lematu o pompowaniu.
01. 04. 2011
Dowod lematu o pompowaniu
Lemat Ogdena ( o pompowaniu kontrolowanym) zastosowania
Zamknietosc i niezamknietosc klasy jez. bezk. na rozne operacje
Jezyk bezk. nad alfabetem 1-elementowym jest regularny
Definicja automatu stosowego (ze stosem), konfiguracje automatu, dzialanie
15.04.2011
Dowod istnienia bezkontekstowego jezyka ktory nie ma jednoznacznej gramatyki bezkontekstowej
Automaty stosowe c.d.
Dowod twierdzenia Parikha:
    jezyki bezkontekstowe sa rownowazne regularnym jesli alfabet jest przemienny
z grubsza dowod wyglada tak:
k - liczba nieterminali, zalozmy postac Chomsky'ego
N stala taka ze slowo dlugosci powyzej N ma sciezke na ktorej
powtarza sie jakis nieterminal k+2 razy (co najmniej)

Niech L(Q) zbior slow majacych wyprowadzenie uzzywajace dokladnie nieterminali ze zbioru Q
F(Q) zbior slow terminalnych xy lacznej dlugosci co najwyzej 2N takich ze
z A mozna wyprowadzic xAy uzywajac tylko nieterminali z Q, dla pewnego A \in Q

T(Q) zbior slow majacych wyprowadzenie uzywajace dokladnie nieterminali ze zbioru Q oraz dlugosc co najwyzej N

Wtedy L(Q) przemiennie rownowazne F(Q)^* T(Q)
Zauwazmy ze te zbiory F(Q), T(Q) sa skonczone

Szukany jezyk regularny jest skonczona suma zbiorow F(Q)^* T(Q)
suma po wszystkich podzbiorach nieterminali (duzo ale skonczenie wiele)
29. 04. 2011
Konstrukcja automatu stosowego rownowaznego gramatyce bezkontekstowej.
Konstrukcja odwrotna.
Przyklady jezykow ktore nie sa deterministycznymi jezykami bezkontekstowymi.
Algorytm Youngera parsingu w czasie O(n^3)
Algorytm w czasie kwadratowym dla gramatyk jednoznacznych.
06.05. 2011
Juwenalia
13. 05. 2011
Przeksztalcanie do postaci normalnej Greibach.`
Maszyny Turinga, definicja.
Podstawowe wersje: jedna tasma, wiele tasm, nieskonczone
w jedna strone, w dwie strony, tasma dwuwymiarowa itp.
Rownowaznosc maszyny Turinga z automatem dwulicznikowym.
Rownowaznosc maszyny Turinga z automatem jednokolejkowym.
20.05. 2011
Kolokwium.