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

• Słowa, katenacja - 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; rozstrzygalność
• Języki bezkontekstowe; własności, gramatyka - postać Chomsky'ego i Greibach i algorytmy do upraszczania; automat ze stosem; równoważność gramatyki bezkontekstowej i automatu ze stosem - algorytmy; lemat o pompowaniu; jednoznaczność, problem przynależności i algorytm CYK; rozstrzygalność
• Języki kontekstowe i typu (0); własności; automat liniowo ograniczony; maszyna Turinga; inne modele obliczeń; Podstawowe klasy złożoności w języku MT; języki rekurencyjnie przeliczalne i rekurencyjne; teza Churcha
• Problemy złożoności i 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. Złożoność obliczeniowa. Języki maszyn Turinga i typu (0). Rozstrzygalność (ćwiczenia)