Forma zajęć
Wykład (30 godzin) + ćwiczenia (30 godzin)
Opis
Teoria jezyków formalnych, automatów i gramatyk w zakresie hierarchii Chomsky'ego.
Sylabus
Autorzy
- Maria Foryś — Uniwersytet Jagielloński
- Wit Foryś — Uniwersytet Jagielloński
- Adam Roman — Uniwersytet Jagielloński
Wymagania wstępne
- Logika i teoria mnogości
- Algebra liniowa z geometrią analityczną
- Matematyka dyskretna
- Algorytmy i struktury danych
Zawartość
- Alfabet, słowo, język - elementy teorii półgrup; półgrupy i monoidy wolne
- Gramatyki – model obliczeń; hierarchia Chomsky'ego
- Języki regularne; automat skończenie stanowy; automat minimalny i algorytmy; automaty deterministyczne i niedeterministyczne; algorytm determinizacji; własności języków regularnych; lemat o pompowaniu i języki nieregularne; wyrażenia regularne i algorytmy; twierdzenie Kleenego; problemy rozstrzygalności
- Języki bezkontekstowe; własności języków bezkontekstowych, gramatyka - postać Chomsky'ego i Greibach oraz algorytmy upraszczania; automat ze stosem; równoważność gramatyki bezkontekstowej i automatu ze stosem - algorytmy; lemat o pompowaniu i języki, które nie są bezkontekstowe; jednoznaczność, problem przynależności i algorytm CYK; problemy rozstrzygalności
- Języki kontekstowe i typu (0); własności; automat liniowo ograniczony; maszyna Turinga i jej wersje
- Podstawowe klasy złożoności w języku maszyn Turinga
- Języki maszyn Turinga i języki typu (0); teza Churcha; problemy rozstrzygalności
Literatura
- M. Foryś, W. Foryś, Teoria automatów i języków formalnych, AOW EXIT, Warszawa 2005.
- J. Gruska, Foundations of computing, Thompson, 1997.
- J.E. Hopcroft, J.D. Ulman, Introduction to automata theory, languages and computing, Addison-Wesley, 1979.
- A. Salomaa, Computation and automata, Cambridge Univ.Press, 1985.
- M. Sipser, Introduction to the theory of computation, PWS Publishing Company, Boston 1997.