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

• 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

Autorzy

• Maria Foryś
• Wit Foryś
• Adam Roman

Wymagania wstępne

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

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ść
• 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.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. Języki, automaty i obliczenia/Wykład 13: Złożoność obliczeniowa. Języki maszyn Turinga i typu (0). Rozstrzygalność (ćwiczenia)
14. Języki maszyn Turinga i typu (0). Rozstrzygalność (ćwiczenia)