Języki automaty i obliczenia

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

  1. M. Foryś, W. Foryś, Teoria automatów i języków formalnych, AOW EXIT, Warszawa 2005.
  2. J. Gruska, Foundations of computing, Thompson, 1997.
  3. J.E. Hopcroft, J.D. Ulman, Introduction to automata theory, languages and computing, Addison-Wesley, 1979.
  4. A. Salomaa, Computation and automata, Cambridge Univ.Press, 1985.
  5. M. Sipser, Introduction to the theory of computation, PWS Publishing Company, Boston 1997.