Języki, automaty i obliczenia
Z Studia Informatyczne
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
- M.Foryś, W.Foryś, Teoria automatów i języków formalnych, AOW EXIT, Warszawa 2005
- J.E.Hopcroft, J.D.Ulman, Introduction to automata theory, languages and computing, Addison-Wesley, 1979
- J.Gruska, Foundations of computing, Thompson, 1997
- A.Salomaa, Computation and Automata, Cambridge Univ.Press, 1985
- M.Sipser, Introduction to the theory of computation, PWS Publishing Company, Boston 1997
Zawartość
- Elementy teorii półgrup (ćwiczenia)
- Gramatyki (ćwiczenia)
- Automat skończenie stanowy I(ćwiczenia)
- Automat skończenie stanowy II(ćwiczenia)
- Lemat o pompowaniu (ćwiczenia)
- Wyrażenia regularne (ćwiczenia)
- Gramatyki regularne(ćwiczenia)
- Języki bezkontekstowe I (ćwiczenia)
- Języki bezkontekstowe II(ćwiczenia)
- Automat ze stosem(ćwiczenia)
- Lemat o pompowaniu, jednoznaczność(ćwiczenia)
- Równania dla języków (ćwiczenia)
- Języki kontekstowe i typu (0) (ćwiczenia)
- Maszyna Turinga(ćwiczenia)
- Problemy rozstrzygalne i nierozstrzygalne (ćwiczenia)
