Języki, automaty i obliczenia: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwaniam (→Zawartość) |
|||
Linia 21: | Linia 21: | ||
* Alfabet, słowo, język - elementy teorii półgrup; półgrupy i monoidy wolne | * Alfabet, słowo, język - elementy teorii półgrup; półgrupy i monoidy wolne | ||
* Gramatyki – model obliczeń; hierarchia Chomsky'ego | * 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; twierdzenie | + | * 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; twierdzenie Kleenego; problemy rozstrzygalności |
− | |||
* Języki bezkontekstowe; własności języków bezkontekstowych, gramatyka - postać Chomsky'ego i Greibach oraz 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 bezkontekstowe; własności języków bezkontekstowych, gramatyka - postać Chomsky'ego i Greibach oraz 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 | * Języki kontekstowe i typu (0); własności; automat liniowo ograniczony; maszyna Turinga i jej wersje |
Aktualna wersja na dzień 12:20, 20 mar 2007
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
- Wit Foryś — Uniwersytet Jagielloński
- Adam Roman — Uniwersytet Jagielloński
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; twierdzenie Kleenego; problemy rozstrzygalności
- Języki bezkontekstowe; własności języków bezkontekstowych, gramatyka - postać Chomsky'ego i Greibach oraz 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
Literatura
- M. Foryś, W. Foryś, Teoria automatów i języków formalnych, AOW EXIT, Warszawa 2005.
- J. Gruska, Foundations of computing, Thompson, 1997.
- J.E. Hopcroft, J.D. Ulman, Introduction to automata theory, languages and computing, Addison-Wesley, 1979.
- A. Salomaa, Computation and automata, Cambridge Univ.Press, 1985.
- M. Sipser, Introduction to the theory of computation, PWS Publishing Company, Boston 1997.
Moduły
- Słowa, katenacja - elementy teorii półgrup, półgrupy i monoidy wolne (ćwiczenia)
- Gramatyka jako model obliczen. Hierarchia Chomsky'ego (ćwiczenia)
- Automat skończenie stanowy (ćwiczenia)
- Wyrażenia regularne. Automat minimalny (ćwiczenia)
- Algorytmy konstrukcji automatu minimalnego (ćwiczenia)
- Automat niedeterministyczny. Lemat o pompowaniu (ćwiczenia)
- Twierdzenie Kleene'ego. Własności języków i gramatyk regularnych (ćwiczenia)
- Dalsze algorytmy dla języków regularnych. Problemy rozstrzygalne (ćwiczenia) (test)
- Języki bezkontekstowe i ich gramatyki (ćwiczenia)
- Lemat o pompowaniu dla języków bezkontekstowych. Własności języków bezkontekstowych. Problemy rozstrzygalne (ćwiczenia)
- Automat ze stosem (ćwiczenia) (test)
- Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga (ćwiczenia)
- Złożoność obliczeniowa. (ćwiczenia)
- Języki maszyn Turinga i typu (0). Rozstrzygalność (ćwiczenia) (test)