Języki, automaty i obliczenia: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Forys (dyskusja | edycje)
60 edycji
Nie podano opisu zmian
Forys (dyskusja | edycje)
60 edycji
 
(Nie pokazano 60 wersji utworzonych przez 6 użytkowników)
Linia 3: Linia 3:


== Opis ==
== Opis ==
wykład prezentuje teorię jezyków formalnych, automatów i gramatyk w zakresie hierarchii Chomsky'ego
Teoria jezyków formalnych, automatów i gramatyk w zakresie hierarchii Chomsky'ego.
 
== Sylabus ==
== Sylabus ==


=== Autorzy ===  
=== Autorzy ===  
* Maria Foryś
* Maria Foryś — Uniwersytet Jagielloński
* Wit Foryś
* Wit Foryś — Uniwersytet Jagielloński
* Adam Roman — Uniwersytet Jagielloński


=== Wymagania wstępne ===
=== Wymagania wstępne ===
Linia 14: Linia 16:
* Algebra liniowa z geometrią analityczną
* Algebra liniowa z geometrią analityczną
* Matematyka dyskretna
* Matematyka dyskretna
 
* Algorytmy i struktury danych


=== Zawartość ===
=== Zawartość ===
* Elementy teorii półgrup; półgrupy i monoidy wolne; podmonoidy monoidów wolnych
* Alfabet, słowo, język - elementy teorii półgrup; półgrupy i monoidy wolne
* Gramatyki – model obliczeń; hierarchia  Chomsky' ego.
* 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 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; twierdzenie Kleenego; problemy rozstrzygalności
* 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ść.
* Języki bezkontekstowe; własności języków bezkontekstowych, gramatyka - postać Chomsky'ego i Greibach oraz algorytmy upraszczania; automat ze stosem; równoważność gramatyki bezkontekstowej i automatu ze stosem - algorytmy; lemat o pompowaniu i języki, które nie są bezkontekstowe; jednoznaczność, problem przynależności  i algorytm CYK; problemy rozstrzygalności
* Równania dla języków – algorytm rozwiązywania
* Języki kontekstowe i typu (0); własności; automat liniowo ograniczony; maszyna Turinga i jej wersje
* Języki kontekstowe i typu (0); własności; automat liniowo ograniczony; maszyna Turinga; konstrukcje; języki rekurencyjnie przeliczalne i rekurencyjne; teza Churcha.
* Podstawowe klasy złożoności w języku maszyn Turinga
* Problemy rozstrzygalne i nierozstrzygalne w teorii języków.
* Języki maszyn Turinga i języki typu (0); teza Churcha; problemy rozstrzygalności
 


=== 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.E.Hopcroft, J.D.Ulman, Introduction to automata theory, languages and computing, Addison-Wesley, 1979  
# J. Gruska, ''Foundations of computing'', Thompson, 1997.
# 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
# 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 ==
* [[ZASD Moduł 1| Elementy teorii półgrup]] (ć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]])
* [[ZASD Moduł 2|Gramatyki ]](ćwiczenia)
# [[Języki, automaty i obliczenia/Wykład 2: Gramatyka jako model obliczen. Hierarchia Chomsky'ego|Gramatyka jako model obliczen. Hierarchia Chomsky'ego]] ([[Języki, automaty i obliczenia/Ćwiczenia 2: Gramatyka jako model obliczen. Hierarchia Chomsky'ego|ćwiczenia]])
* [[ZASD Moduł 3|Automat skończenie stanowy I]](ćwiczenia)
# [[Języki, automaty i obliczenia/Wykład 3: Automat skończenie stanowy|Automat skończenie stanowy]] ([[Języki, automaty i obliczenia/Ćwiczenia 3: Automat skończenie stanowy|ćwiczenia]])
* [[ZASD Moduł 4|Automat skończenie stanowy II]](ćwiczenia)
# [[Języki, automaty i obliczenia/Wykład 4: Wyrażenia regularne. Automat minimalny|Wyrażenia regularne. Automat minimalny]] ([[Języki, automaty i obliczenia/Ćwiczenia 4: Wyrażenia regularne. Automat minimalny|ćwiczenia]])
* [[ZASD Moduł 5|Lemat o pompowaniu ]](ćwiczenia)
# [[Języki, automaty i obliczenia/Wykład 5: Algorytmy konstrukcji automatu minimalnego|Algorytmy konstrukcji automatu minimalnego]] ([[Języki, automaty i obliczenia/Ćwiczenia 5: Algorytmy konstrukcji automatu minimalnego|ćwiczenia]])
* [[ZASD Moduł 6|Wyrażenia regularne ]](ćwiczenia)
# [[Języki, automaty i obliczenia/Wykład 6: Automat niedeterministyczny. Lemat o pompowaniu|Automat niedeterministyczny. Lemat o pompowaniu]] ([[Języki, automaty i obliczenia/Ćwiczenia 6: Automat niedeterministyczny. Lemat o pompowaniu|ćwiczenia]])
* [[ZASD Moduł 7|Gramatyki regularne]](ćwiczenia)
# [[Języki, automaty i obliczenia/Wykład 7: Twierdzenie Kleene'ego. Własności języków i gramatyk regularnych|Twierdzenie Kleene'ego. Własności języków i gramatyk regularnych]] ([[Języki, automaty i obliczenia/Ćwiczenia 7: Twierdzenie Kleene'ego. Własności języków i gramatyk regularnych|ćwiczenia]])
* [[ZASD Moduł 8|Języki bezkontekstowe I ]](ćwiczenia)
# [[Języki, automaty i obliczenia/Wykład 8: Dalsze algorytmy dla języków regularnych. Problemy rozstrzygalne|Dalsze algorytmy dla języków regularnych. Problemy rozstrzygalne]] ([[Języki, automaty i obliczenia/Ćwiczenia 8: Dalsze algorytmy dla języków regularnych. Problemy rozstrzygalne|ćwiczenia]]) ([[Języki, automaty i obliczenia/Test 8: Dalsze algorytmy dla języków regularnych. Problemy rozstrzygalne|test]])
* [[ZASD Moduł 9|Języki bezkontekstowe II]](ćwiczenia)
# [[Języki, automaty i obliczenia/Wykład 9: Języki bezkontekstowe i ich gramatyki|Języki bezkontekstowe i ich gramatyki]] ([[Języki, automaty i obliczenia/Ćwiczenia 9: Języki bezkontekstowe i ich gramatyki|ćwiczenia]])
* [[ZASD Moduł 10|Automat ze stosem]](ćwiczenia)
# [[Języki, automaty i obliczenia/Wykład 10: Lemat o pompowaniu dla języków bezkontekstowych. Własności języków bezkontekstowych. Problemy rozstrzygalne|Lemat o pompowaniu dla języków bezkontekstowych. Własności języków bezkontekstowych. Problemy rozstrzygalne]] ([[Języki, automaty i obliczenia/Ćwiczenia 10: Lemat o pompowaniu dla języków bezkontekstowych. Własności języków bezkontekstowych. Problemy rozstrzygalne |ćwiczenia]])
* [[ZASD Moduł 11|Lemat o pompowaniu, jednoznaczność]](ćwiczenia)
# [[Języki, automaty i obliczenia/Wykład 11: Automat ze stosem|Automat ze stosem]] ([[Języki, automaty i obliczenia/Ćwiczenia 11: Automat ze stosem|ćwiczenia]]) ([[Języki, automaty i obliczenia/Test 11: Automat ze stosem|test]])
* [[ZASD Moduł 12|Równania dla języków ]](ćwiczenia)
# [[Języki, automaty i obliczenia/Wykład 12: Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga |Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga]] ([[Języki, automaty i obliczenia/Ćwiczenia 12: Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga|ćwiczenia]])
* [[ZASD Moduł 13|Języki kontekstowe i typu (0)]] (ćwiczenia)
# [[Języki, automaty i obliczenia/Wykład 13: Złożoność obliczeniowa. |Złożoność obliczeniowa.]] ([[Języki, automaty i obliczenia/Ćwiczenia 13:  Złożoność obliczeniowa.|ćwiczenia]])
* [[ZASD Moduł 14|Maszyna Turinga]](ćwiczenia)
# [[Języki, automaty i obliczenia/Wykład 14: Języki maszyn Turinga i typu (0). Rozstrzygalność|Języki maszyn Turinga i typu (0). Rozstrzygalność]] ([[Języki, automaty i obliczenia/Ćwiczenia 14: Języki maszyn Turinga i typu (0). Rozstrzygalność|ćwiczenia]]) ([[Języki, automaty i obliczenia/Test 14: Języki maszyn Turinga i typu (0). Rozstrzygalność|test]])
* [[ZASD Moduł 15|Problemy rozstrzygalne i nierozstrzygalne]] (ćwiczenia)

Aktualna wersja na dzień 12:20, 20 mar 2007

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ś — Uniwersytet Jagielloński
  • Wit Foryś — Uniwersytet Jagielloński
  • Adam Roman — Uniwersytet Jagielloński

Wymagania wstępne

  • Logika i teoria mnogości
  • Algebra liniowa z geometrią analityczną
  • Matematyka dyskretna
  • Algorytmy i struktury danych

Zawartość

  • Alfabet, słowo, język - 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; twierdzenie Kleenego; problemy rozstrzygalności
  • Języki bezkontekstowe; własności języków bezkontekstowych, gramatyka - postać Chomsky'ego i Greibach oraz algorytmy upraszczania; automat ze stosem; równoważność gramatyki bezkontekstowej i automatu ze stosem - algorytmy; lemat o pompowaniu i języki, które nie są bezkontekstowe; jednoznaczność, problem przynależności i algorytm CYK; problemy rozstrzygalności
  • Języki kontekstowe i typu (0); własności; automat liniowo ograniczony; maszyna Turinga i jej wersje
  • Podstawowe klasy złożoności w języku maszyn Turinga
  • Języki maszyn Turinga i języki typu (0); teza Churcha; problemy rozstrzygalności

Literatura

  1. M. Foryś, W. Foryś, Teoria automatów i języków formalnych, AOW EXIT, Warszawa 2005.
  2. J. Gruska, Foundations of computing, Thompson, 1997.
  3. J.E. Hopcroft, J.D. Ulman, Introduction to automata theory, languages and computing, Addison-Wesley, 1979.
  4. A. Salomaa, Computation and automata, Cambridge Univ.Press, 1985.
  5. M. Sipser, Introduction to the theory of computation, PWS Publishing Company, Boston 1997.

Moduły

  1. Słowa, katenacja - elementy teorii półgrup, półgrupy i monoidy wolne (ćwiczenia)
  2. Gramatyka jako model obliczen. Hierarchia Chomsky'ego (ćwiczenia)
  3. Automat skończenie stanowy (ćwiczenia)
  4. Wyrażenia regularne. Automat minimalny (ćwiczenia)
  5. Algorytmy konstrukcji automatu minimalnego (ćwiczenia)
  6. Automat niedeterministyczny. Lemat o pompowaniu (ćwiczenia)
  7. Twierdzenie Kleene'ego. Własności języków i gramatyk regularnych (ćwiczenia)
  8. Dalsze algorytmy dla języków regularnych. Problemy rozstrzygalne (ćwiczenia) (test)
  9. Języki bezkontekstowe i ich gramatyki (ćwiczenia)
  10. Lemat o pompowaniu dla języków bezkontekstowych. Własności języków bezkontekstowych. Problemy rozstrzygalne (ćwiczenia)
  11. Automat ze stosem (ćwiczenia) (test)
  12. Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga (ćwiczenia)
  13. Złożoność obliczeniowa. (ćwiczenia)
  14. Języki maszyn Turinga i typu (0). Rozstrzygalność (ćwiczenia) (test)
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Języki,_automaty_i_obliczenia&oldid=69522”