Teoria języków formalnych i automatów
Napisa�: Maciej Muras   
Thursday, 24 May 2007
TEORIA JĘZYKÓW FORMALNYCH I AUTOMATÓWPrzedmiot: obowiązkowy

Formy nauczania: wykład, konwersatorium

Czas trwania: rok III semestr piąty, 2 godz. wyk. + 2 godz. ćw./tyg. (Razem 60godz.)Zaliczenie przedmiotu: zaliczenie konwersatorium na ocen

ę i egzamin

Opis przedmiotu:

1. Wprowadzenie - alfabety i języki, operacje na językach, domknięcie Kleene'go.2. Języki regularne - wyraŜenia regularne, języki regularne, automaty skończone,

twierdzenie Kleenee'go.

3.
Własności języków regularnych - lemat o pompowaniu, twierdzenie Myhilla-

Nerode'a.

4. Determinizacja automatów skończonych - równowaŜność DAS i NAS,minimalizacja DAS, własno

ści domknięcia klasy języków regularnych. 5. Maszyny Turinga - model maszyny Turinga; języki i funkcje obliczalne;

nierozstrzygalność problemu stopu; teza Churcha.

LITERATURA

[1] A.Aho, J. E. Hopcroft, J. D. Ullman, Projektowanie i analiza algorytmów komputerowych,

PWN, Warszawa 1983

[2] J.E. Hopcroft, J.D. Ullman, Wprowadzenie do teorii automatów i obliczeń, PWN, 1994