Mikołaj Bojańczyk > Języki, Automaty i Obliczenia (wykład 2010)

Języki, Automaty i Obliczenia

15 lutego: Definicja automatu

22 lutego: Determinizacja. Wyrażenia regularne.

1 marca: Twierdzenie Kleene'go o równoważności wyrażeń regularnych i automatów.

8 marca: Lemat o pompowaniu. Minimalizacja automatów.

15 marca: Zakończenie języków regularnych. Początek gramatyk bezkontekstowych.

22 marca: Gramatyki. Drzewa wyprowadzeń.

29 marca: Automaty ze stosem. Równoważność z gramatykami.

5 kwietnia: Lany poniedziałek

12 kwietnia: Pompowanie języków bezkontekstowych.

19 kwietnia: Postacie normalne gramatyk. Algorytm CYK. Języki kontekstowe.

26 kwietnia: Maszyna Turinga

3 maja: 3 maja

10 maja: Nierozstrzygalność.

17 maja: Kolokwium. Rozwiązania

24 maja: Nierozstrzygalność problemu Posta.

31 maja: Klasy złożoności: NP.