Języki, automaty i obliczenia: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 35: | Linia 35: | ||
=== Moduły === | === Moduły === | ||
* [[ZASD Moduł 1| Elementy teorii półgrup]] (ćwiczenia) | * [[ZASD Moduł 1| Elementy teorii półgrup]] ([[ZASD Ćwiczenia 1|ćwiczenia]]) | ||
* [[ZASD Moduł 2|Gramatyki ]](ćwiczenia) | * [[ZASD Moduł 2|Gramatyki ]]([[ZASD Ćwiczenia 2|ćwiczenia]]) | ||
* [[ZASD Moduł 3|Automat skończenie stanowy I]](ćwiczenia) | * [[ZASD Moduł 3|Automat skończenie stanowy I]]([[ZASD Ćwiczenia 3|ćwiczenia]]) | ||
* [[ZASD Moduł 4|Automat skończenie stanowy II]](ćwiczenia) | * [[ZASD Moduł 4|Automat skończenie stanowy II]]([[ZASD Ćwiczenia 4|ćwiczenia]]) | ||
* [[ZASD Moduł 5|Lemat o pompowaniu ]](ćwiczenia) | * [[ZASD Moduł 5|Lemat o pompowaniu ]]([[ZASD Ćwiczenia 5|ćwiczenia]]) | ||
* [[ZASD Moduł 6|Wyrażenia regularne ]](ćwiczenia) | * [[ZASD Moduł 6|Wyrażenia regularne ]]([[ZASD Ćwiczenia 6|ćwiczenia]]) | ||
* [[ZASD Moduł 7|Gramatyki regularne]](ćwiczenia) | * [[ZASD Moduł 7|Gramatyki regularne]]([[ZASD Ćwiczenia 7|ćwiczenia]]) | ||
* [[ZASD Moduł 8|Języki bezkontekstowe I ]](ćwiczenia) | * [[ZASD Moduł 8|Języki bezkontekstowe I ]]([[ZASD Ćwiczenia 8|ćwiczenia]]) | ||
* [[ZASD Moduł 9|Języki bezkontekstowe II]](ćwiczenia) | * [[ZASD Moduł 9|Języki bezkontekstowe II]]([[ZASD Ćwiczenia 9|ćwiczenia]]) | ||
* [[ZASD Moduł 10|Automat ze stosem]](ćwiczenia) | * [[ZASD Moduł 10|Automat ze stosem]]([[ZASD Ćwiczenia 10|ćwiczenia]]) | ||
* [[ZASD Moduł 11|Lemat o pompowaniu, jednoznaczność]](ćwiczenia) | * [[ZASD Moduł 11|Lemat o pompowaniu, jednoznaczność]]([[ZASD Ćwiczenia 11|ćwiczenia]]) | ||
* [[ZASD Moduł 12|Równania dla języków ]](ćwiczenia) | * [[ZASD Moduł 12|Równania dla języków ]]([[ZASD Ćwiczenia 12|ćwiczenia]]) | ||
* [[ZASD Moduł 13|Języki kontekstowe i typu (0)]] (ćwiczenia) | * [[ZASD Moduł 13|Języki kontekstowe i typu (0)]] ([[ZASD Ćwiczenia 13|ćwiczenia]]) | ||
* [[ZASD Moduł 14|Maszyna Turinga]](ćwiczenia) | * [[ZASD Moduł 14|Maszyna Turinga]]([[ZASD Ćwiczenia 14|ćwiczenia]]) | ||
* [[ZASD Moduł 15|Problemy rozstrzygalne i nierozstrzygalne]] (ćwiczenia) | * [[ZASD Moduł 15|Problemy rozstrzygalne i nierozstrzygalne]] ([[ZASD Ćwiczenia 15|ćwiczenia]]) | ||
Wersja z 12:31, 15 cze 2006
Forma zajęć
Wykład (30 godzin) + ćwiczenia (30 godzin)
Opis
wykład prezentuje teorię jezyków formalnych, automatów i gramatyk w zakresie hierarchii Chomsky'ego
Sylabus
Autorzy
- Maria Foryś
- Wit Foryś
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; własności; lemat o pompowaniu i języki nieregularne; wyrażenia regularne; tw. Kleene.
- Języki bezkontekstowe; własności, 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); własności; automat liniowo ograniczony; maszyna Turinga; konstrukcje; 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)
