Języki, automaty i obliczenia: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| 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.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 09:08, 9 lip 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ś
- 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
- 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
- Elementy teorii półgrup (ćwiczenia)
- Gramatyki (ćwiczenia)
- Automat skończenie stanowy I (ćwiczenia)
- Automat skończenie stanowy II (ćwiczenia)
- Lemat o pompowaniu (ćwiczenia)
- Wyrażenia regularne (ćwiczenia)
- Gramatyki regularne (ćwiczenia)
- Języki bezkontekstowe I (ćwiczenia)
- Języki bezkontekstowe II (ćwiczenia)
- Automat ze stosem (ćwiczenia)
- Lemat o pompowaniu, jednoznaczność (ćwiczenia)
- Równania dla języków (ćwiczenia)
- Języki kontekstowe i typu (0) (ćwiczenia)
- Maszyna Turinga (ćwiczenia)
- Problemy rozstrzygalne i nierozstrzygalne (ćwiczenia)
