Teoria automatów

Język wykładowy Polski
Semestr Zimowy
Status Poddana pod głosowanie
Opiekun Jan Otop
Liczba godzin 30 (wyk.) 30 (ćw.)
Rodzaj I2.T - teoria inf.
ECTS 6
Polecany dla I roku Nie
Egzamin Tak

Opis przedmiotu:

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.