Języki, automaty i obliczenia: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwaniam (→Zawartość) |
|||
| Linia 29: | Linia 29: | ||
=== Literatura === | === Literatura === | ||
| − | # M.Foryś, W.Foryś, Teoria automatów i języków formalnych, AOW EXIT, Warszawa 2005 | + | # M. Foryś, W. Foryś, ''Teoria automatów i języków formalnych'', AOW EXIT, Warszawa 2005. |
| − | # J.Gruska, Foundations of computing, Thompson, 1997 | + | # J. Gruska, ''Foundations of computing'', Thompson, 1997. |
| − | # J.E.Hopcroft, J.D.Ulman, Introduction to automata theory, languages and computing, Addison-Wesley, 1979 | + | # 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 | + | # A. Salomaa, ''Computation and automata'', Cambridge Univ.Press, 1985. |
| − | # M.Sipser, Introduction to the theory of computation, PWS Publishing Company, Boston 1997 | + | # M. Sipser, ''Introduction to the theory of computation'', PWS Publishing Company, Boston 1997. |
== Moduły == | == Moduły == | ||
Wersja z 19:38, 27 wrz 2006
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 Kleene
go; 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)
