Języki, automaty i obliczenia: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 42: | Linia 42: | ||
== Moduły == | == Moduły == | ||
[[Języki, automaty i obliczenia/Wykład 1 Słowa, katenacja - elementy teorii półgrup, półgrupy i monoidy wolne|Słowa, katenacja - elementy teorii półgrup, półgrupy i monoidy wolne ]] ([[Języki, automaty i obliczenia/Ćwiczenia 1 Słowa, katenacja - elementy teorii półgrup, półgrupy i monoidy wolne|ćwiczenia]]) | [[Języki, automaty i obliczenia/Wykład 1 Słowa, katenacja - elementy teorii półgrup, półgrupy i monoidy wolne|Słowa, katenacja - elementy teorii półgrup, półgrupy i monoidy wolne ]] ([[Języki, automaty i obliczenia/Ćwiczenia 1 Słowa, katenacja - elementy teorii półgrup, półgrupy i monoidy wolne|ćwiczenia]]) | ||
* [[ | * [[Języki, automaty i obliczenia/Wykład 2 Gramatyki - modele obliczeń, hierarchia Chomsky' ego|Gramatyki - modele obliczeń, hierarchia Chomsky' ego ]]([[ZASD Ćwiczenia 2|ćwiczenia]]) | ||
* [[ | * [[Języki, automaty i obliczenia/Wykład 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]]) | ||
* [[ | * [[Języki, automaty i obliczenia/Wykład 5|Lemat o pompowaniu ]] ([[ZASD Ćwiczenia 5|ćwiczenia]]) | ||
* [[ | * [[Języki, automaty i obliczenia/Wykład 6|Wyrażenia regularne ]] ([[ZASD Ćwiczenia 6|ćwiczenia]]) | ||
* [[ | * [[Języki, automaty i obliczenia/Wykład 7|Gramatyki regularne]] ([[ZASD Ćwiczenia 7|ćwiczenia]]) | ||
* [[ | * [[Języki, automaty i obliczenia/Wykład 8|Języki bezkontekstowe I ]] ([[ZASD Ćwiczenia 8|ćwiczenia]]) | ||
* [[ | * [[Języki, automaty i obliczenia/Wykład 9|Języki bezkontekstowe II]] ([[ZASD Ćwiczenia 9|ćwiczenia]]) | ||
* [[ | * [[Języki, automaty i obliczenia/Wykład 10|Automat ze stosem]] ([[ZASD Ćwiczenia 10|ćwiczenia]]) | ||
* [[ | * [[Języki, automaty i obliczenia/Wykład 11|Lemat o pompowaniu, jednoznaczność]] ([[ZASD Ćwiczenia 11|ćwiczenia]]) | ||
* [[ | * [[Języki, automaty i obliczenia/Wykład 12|Równania dla języków ]] ([[ZASD Ćwiczenia 12|ćwiczenia]]) | ||
* [[ | * [[Języki, automaty i obliczenia/Wykład 13|Języki kontekstowe i typu (0)]] ([[ZASD Ćwiczenia 13|ćwiczenia]]) | ||
* [[ | * [[Języki, automaty i obliczenia/Wykład 14|Maszyna Turinga]] ([[ZASD Ćwiczenia 14|ćwiczenia]]) | ||
* [[ | * [[Języki, automaty i obliczenia/Wykład|Problemy rozstrzygalne i nierozstrzygalne]] ([[ZASD Ćwiczenia 15|ćwiczenia]]) | ||
Wersja z 11:20, 3 sie 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
- Słowa, katenacja - 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; tw. Kleene; rozstrzygalność
- Języki bezkontekstowe; własności, gramatyka - postać Chomsky'ego i Greibach i algorytmy do upraszczania; automat ze stosem; równoważność gramatyki bezkontekstowej i automatu ze stosem - algorytmy; lemat o pompowaniu; jednoznaczność, problem przynależności i algorytm CYK; rozstrzygalność
- Języki kontekstowe i typu (0); własności; automat liniowo ograniczony; maszyna Turinga; inne modele obliczeń; Podstawowe klasy złożoności w języku MT; języki rekurencyjnie przeliczalne i rekurencyjne; teza Churcha
- Problemy złożoności i problemy rozstrzygalności w teorii języków
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
Słowa, katenacja - elementy teorii półgrup, półgrupy i monoidy wolne (ćwiczenia)
- Gramatyki - modele obliczeń, hierarchia Chomsky' ego (ć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)
