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 37: | Linia 37: | ||
* [[ZASD Moduł 1| Elementy teorii półgrup]] ([[ZASD Ćwiczenia 1|ćwiczenia]]) | * [[ZASD Moduł 1| Elementy teorii półgrup]] ([[ZASD Ćwiczenia 1|ćwiczenia]]) | ||
* [[ZASD Moduł 2|Gramatyki ]]([[ZASD Ćwiczenia 2|ćwiczenia]]) | * [[ZASD Moduł 2|Gramatyki ]]([[ZASD Ćwiczenia 2|ćwiczenia]]) | ||
* [[ZASD Moduł 3|Automat skończenie stanowy I]]([[ZASD Ćwiczenia 3|ćwiczenia]]) | * [[ZASD Moduł 3|Automat skończenie stanowy I]] ([[ZASD Ćwiczenia 3|ćwiczenia]]) | ||
* [[ZASD Moduł 4|Automat skończenie stanowy II]]([[ZASD Ćwiczenia 4|ćwiczenia]]) | * [[ZASD Moduł 4|Automat skończenie stanowy II]] ([[ZASD Ćwiczenia 4|ćwiczenia]]) | ||
* [[ZASD Moduł 5|Lemat o pompowaniu ]]([[ZASD Ćwiczenia 5|ćwiczenia]]) | * [[ZASD Moduł 5|Lemat o pompowaniu ]] ([[ZASD Ćwiczenia 5|ćwiczenia]]) | ||
* [[ZASD Moduł 6|Wyrażenia regularne ]]([[ZASD Ćwiczenia 6|ćwiczenia]]) | * [[ZASD Moduł 6|Wyrażenia regularne ]] ([[ZASD Ćwiczenia 6|ćwiczenia]]) | ||
* [[ZASD Moduł 7|Gramatyki regularne]]([[ZASD Ćwiczenia 7|ćwiczenia]]) | * [[ZASD Moduł 7|Gramatyki regularne]] ([[ZASD Ćwiczenia 7|ćwiczenia]]) | ||
* [[ZASD Moduł 8|Języki bezkontekstowe I ]]([[ZASD Ćwiczenia 8|ćwiczenia]]) | * [[ZASD Moduł 8|Języki bezkontekstowe I ]] ([[ZASD Ćwiczenia 8|ćwiczenia]]) | ||
* [[ZASD Moduł 9|Języki bezkontekstowe II]]([[ZASD Ćwiczenia 9|ćwiczenia]]) | * [[ZASD Moduł 9|Języki bezkontekstowe II]] ([[ZASD Ćwiczenia 9|ćwiczenia]]) | ||
* [[ZASD Moduł 10|Automat ze stosem]]([[ZASD Ćwiczenia 10|ćwiczenia]]) | * [[ZASD Moduł 10|Automat ze stosem]] ([[ZASD Ćwiczenia 10|ćwiczenia]]) | ||
* [[ZASD Moduł 11|Lemat o pompowaniu, jednoznaczność]]([[ZASD Ćwiczenia 11|ćwiczenia]]) | * [[ZASD Moduł 11|Lemat o pompowaniu, jednoznaczność]] ([[ZASD Ćwiczenia 11|ćwiczenia]]) | ||
* [[ZASD Moduł 12|Równania dla języków ]]([[ZASD Ćwiczenia 12|ćwiczenia]]) | * [[ZASD Moduł 12|Równania dla języków ]] ([[ZASD Ćwiczenia 12|ćwiczenia]]) | ||
* [[ZASD Moduł 13|Języki kontekstowe i typu (0)]] ([[ZASD Ćwiczenia 13|ćwiczenia]]) | * [[ZASD Moduł 13|Języki kontekstowe i typu (0)]] ([[ZASD Ćwiczenia 13|ćwiczenia]]) | ||
* [[ZASD Moduł 14|Maszyna Turinga]]([[ZASD Ćwiczenia 14|ćwiczenia]]) | * [[ZASD Moduł 14|Maszyna Turinga]] ([[ZASD Ćwiczenia 14|ćwiczenia]]) | ||
* [[ZASD Moduł 15|Problemy rozstrzygalne i nierozstrzygalne]] ([[ZASD Ćwiczenia 15|ćwiczenia]]) | * [[ZASD Moduł 15|Problemy rozstrzygalne i nierozstrzygalne]] ([[ZASD Ćwiczenia 15|ćwiczenia]]) | ||
Wersja z 12:34, 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)
