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, Wydział Matematyki i Informatyki, Instytut Informatyki,
• Wit Foryś - Uniwersytet Jagielloński, Wydział Matematyki i Informatyki, Instytut Informatyki,
• Adam Roman - Uniwersytet Jagielloński, Wydział Matematyki i Informatyki, Instytut Informatyki,

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; tw. Kleene; problemy rozstrzygalności
• Języki bezkontekstowe; własności języków bezkontekstowych, gramatyka - postać Chomsky'ego i Greibach i 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 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.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

Moduły

1. Słowa, katenacja - elementy teorii półgrup, półgrupy i monoidy wolne (ćwiczenia)
2. Gramatyka jako model obliczen. Hierarchia Chomsky'ego (ćwiczenia)
3. Automat skończenie stanowy (ćwiczenia)
4. Wyrażenia regularne. Automat minimalny (ćwiczenia)
5. Algorytmy konstrukcji automatu minimalnego (ćwiczenia)
6. Automat niedeterministyczny. Lemat o pompowaniu (ćwiczenia)
7. Twierdzenie Kleene'ego. Własności języków i gramatyk regularnych (ćwiczenia)
8. Dalsze algorytmy dla języków regularnych. Problemy rozstrzygalne (ćwiczenia)
9. Języki bezkontekstowe i ich gramatyki (ćwiczenia)
10. Lemat o pompowaniu dla języków bezkontekstowych. Własności języków bezkontekstowych. Problemy rozstrzygalne (ćwiczenia)
11. Automat ze stosem (ćwiczenia)
12. Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga (ćwiczenia)
13. Złożoność obliczeniowa. (ćwiczenia)
14. Języki maszyn Turinga i typu (0). Rozstrzygalność (ćwiczenia)