Wykład będzie dotyczył klasycznych wyników z teorii automatów skończonych oraz bardziej zaawansowanych modeli automatów. Część zagadnień pojawia się na JFiZO a na tych zajęciach zostaną omówione dogłębniej.
Na przykład:
- Każdy NFA można przekształcić do równoważnego wyrażenia regularnego i vice versa. Jak się ma rozmiar NFA do rozmiaru wyrażenie regularnego?
- Języki regularne spełniają lemat o pompowaniu. Czy zachodzi twierdzenie odwrotne?
Program:
Automaty skończone:
a) Równoważne definicje języków regularnych: automaty, wyrażenie regularne, WMSO i monoidy.
b) Twierdzenia Kleene'go, Myhilla-Neroda i ich zastosowania.
c) Uczenie się automatów.
d) Minimalizacja automatów.
Automaty na słowach nieskończonych.
a) Automaty Buchiego oraz inne warunki akceptacji.
b) Zamkniętość języków omega-regularnych ze względu na sumę, przekrój, dopełnienie.
c) Determinizacja automatów na słowach nieskończonych.
Automaty na drzewach oraz drzewach nieskończonych.
a) Podstawowe definicje i własności.
b) Związki automatów na drzewach z grami na grafach.
Gry na grafach.
a) Podstawowe definicje.
b) Strategie: bezpamięciowe, ze skończoną pamięcią oraz z nieskończoną pamięcią.
Automaty z wagami.
a) Podstawowe definicje.
b) Zastosowania w rozpoznawaniu mowy i weryfikacji.
