JAO: co bylo na wykladzie

Wyklad 1
Nieformalna dyskusja tego co bedzie na wykladach.
Podstawowe operacje na slowach i jezykach formalnych.
Definicja jezykow regularnych.
Definicja wyrazen regularnych.
Roznice miedzy rozszerzonymi i standardowymi wyrazeniami.

Wyklad2

Definicja deterministycznych i niedeterministycznych automatow skonczonych.
Determinizacja - konstrukcja potegowa.
Przyklady automatow.

Wyklad3

Ilorazy
Lemat o pompowaniu
Dowodzenie nieregularnosci jezyka.
Przyklady automatow niedeterministycznych trudnych do determinizacji.
Przyklad determinizacji - cykliczny zamek (problem barmana)
dla dowolnego n.

Wyklad4

Synteza automatu.
Analiza automatu.

Wyklad5

Minimalizacja automatow.
Rownowaznosc automatow.
"Algorytm" Brzozowskiego.

Wyklad6

Wprowadzenie gramatyk.
Przyklady gramatyk bezkontekstowych.