Wykład 1 (4.X 2025)
-
Przegląd tematyki.
Alfabety, słowa, języki.
Automaty skończone deterministyczne, niedeterministyczne, z cichymi przejściami.
Wyrażenia regularne. Tw. Kleene'ego (wszystkie powyższe metody definiują tę samą klasę języków). Wykład 2 (18.X 2025)
- Języki regularne, c.d. Operacje na językach regularnych. Lemat o pompowaniu.
- Języki bezkontekstowe i gramatyki. Automaty ze stosami. Operacje na językach bezkontekstowych. Lemat o pompowaniu.
Wykład 3 (25.X 2025)
- Maszyny Turinga. Porównanie maszyn Turinga z innymi klasami automatów. Języki rekurencyjnie przeliczalne i rekurencyjne. Rozstrzygalność. Obliczalność.
