Języki, automaty i obliczenia

Z Studia Informatyczne
Wersja z dnia 07:58, 7 lip 2006 autorstwa Ciebie (dyskusja | edycje) (Poprawki edytorskie)
Przejdź do nawigacjiPrzejdź do wyszukiwania

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ś
  • Wit Foryś
  • Adam Roman

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, lemat o pompowaniu i języki nieregularne, wyrażenia regularne, tw. Kleene
  • Języki bezkontekstowe, 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), automat liniowo ograniczony, maszyna Turinga, 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=3019”