Języki, automaty i obliczenia

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Forma zajęć

Wykład (30 godzin) + ćwiczenia (30 godzin)

Opis

wykład prezentuje teorię jezyków formalnych, automatów i gramatyk w zakresie hierarchii Chomsky'ego

Sylabus

Autorzy

  • Maria Foryś
  • Wit Foryś

Wymagania wstępne

  • Logika i teoria mnogości
  • Algebra liniowa z geometrią analityczną
  • Matematyka dyskretna


Zawartość

  • Elementy teorii półgrup; półgrupy i monoidy wolne; podmonoidy monoidów wolnych
  • Gramatyki – model obliczeń; hierarchia Chomsky' ego.
  • Języki regularne; automat skończenie stanowy; automat minimalny–algorytm konstrukcji; automaty deterministyczne i niedeterministyczne; własności; lemat o pompowaniu i języki nieregularne; wyrażenia regularne; tw. Kleene.
  • Języki bezkontekstowe; własności, gramatyka - postać Chomsky'ego i Greibach; automat ze stosem; równoważność gramatyki bezkontekstowej i automatu ze stosem - algorytmy; lemat o pompowaniu; jednoznaczność.
  • Równania dla języków – algorytm rozwiązywania
  • Języki kontekstowe i typu (0); własności; automat liniowo ograniczony; maszyna Turinga; konstrukcje; języki rekurencyjnie przeliczalne i rekurencyjne; teza Churcha.
  • Problemy rozstrzygalne i nierozstrzygalne w teorii języków.


Literatura

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


Moduły

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Języki,_automaty_i_obliczenia&oldid=2115”