Wykład 1 (28.II 2026)
Automaty skończone. Języki regularne.
Wykład 2 (21.III 2026)
Języki regularne i nieregularne: lemat o pompowaniu.
Wyrażenia regularne.Wykład 3 (28.III 2026)
Twierdzenie Myhilla-Nerode’a.
Zastosowania wyrażeń regularnych.Wykład 4 (11.IV 2026)
Gramatyki bezkontekstowe, postać kanoniczna, jednoznaczność.
Lemat o pompowaniu i przykłady języków nie bezkontekstowych.Wykład 5 (25.IV 2026)
Automaty (niedeterministyczne) ze stosem. Równoważność gramatyk bezkontekstowych i tych automatów. Operacje na językach bezkontekstowych.
Wykład 6 (9.V 2026)
Automaty deterministyczne ze stosem.
Algorytmy decyzyjne dla różnych klas języków.
Wykład 7 (16.V 2026)
-
Nierozstrzygalność -- Uniwersalna Maszyna Turinga.
Wykład 8 (30.V 2026)
-
Nierozstrzygalność -- własność stopu i inne.
Wykład 9 (13.VI 2026)
- Podsumowanie.
