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ść
• 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.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. Gramatyki - modele obliczeń, hierarchia Chomsky' ego (ćwiczenia)
3. Automat skończenie stanowy I (ćwiczenia)
4. Automat skończenie stanowy II (ćwiczenia)
5. Algorytmy konstrukcji automatu minimalnego (ćwiczenia)
6. Automat niedeterministyczny; lemat o pompowaniu (ćwiczenia)
7. Twierdzenie Kleene’ego; gramatyki regularne (ćwiczenia)
8. Gramatyka regularna i wyrażenia - algorytmy; rozstrzygalność (ćwiczenia)
9. Języki i gramatyki bezkontekstowe (ćwiczenia)
10. Automat ze stosem (ćwiczenia)
11. Lemat o pompowaniu dla języków bezkontekstowych; jednoznaczność (ćwiczenia)
12. Języki kontekstowe i typu 0; maszyna Turinga (ćwiczenia)
13. Problemy rozstrzygalne i nierozstrzygalne w teorii języków (ćwiczenia)