Wykład będzie dotyczył klasycznych wyników z teorii automatów skończonych oraz bardziej zaawansowanych modeli automatów. Część zagadnień została zasygnalizowana na JFiZO a my przyglądniemy się im dokładniej.
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:
1. Automaty skończone:
* Równoważne definicje języków regularnych: automaty, wyrażenie regularne, WMSO i monoidy.
* Twierdzenia Kleene'go, Myhilla-Neroda i ich zastosowania.
* Uczenie się automatów.
* Minimalizacja automatów.
2. Automaty na słowach nieskończonych.
* Automaty Buchiego oraz inne warunki akceptacji.
* Zamkniętość języków omega-regularnych ze względu na sumę, przekrój, dopełnienie.
* Determinizacja automatów na słowach nieskończonych.
3. Automaty na drzewach oraz drzewach nieskończonych.
* Podstawowe definicje i własności.
* Związki automatów na drzewach z grami na grafach.
4. Gry na grafach.
* Podstawowe definicje.
* Strategie: bezpamięciowe, ze skończoną pamięcią oraz z nieskończoną pamięcią.
5. Automaty z wagami.
* Podstawowe definicje.
* Zastosowania w rozpoznawaniu mowy i weryfikacji.
