Języki, automaty i obliczenia: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m Poprawki edytorskie |
|||
| Linia 18: | Linia 18: | ||
=== Zawartość === | === Zawartość === | ||
* Elementy teorii półgrup | * Elementy teorii półgrup, półgrupy i monoidy wolne, podmonoidy monoidów wolnych | ||
* Gramatyki – model obliczeń | * Gramatyki – model obliczeń, hierarchia Chomsky' ego | ||
* Języki regularne | * 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 | * 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 | * Równania dla języków - algorytm rozwiązywania | ||
* Języki kontekstowe i typu (0) | * 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 | * Problemy rozstrzygalne i nierozstrzygalne w teorii języków | ||
=== Literatura === | === Literatura === | ||
Wersja z 07:58, 7 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
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.E.Hopcroft, J.D.Ulman, Introduction to automata theory, languages and computing, Addison-Wesley, 1979
- J.Gruska, Foundations of computing, Thompson, 1997
- 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)
