Języki, automaty i obliczenia

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

1. M.Foryś, W.Foryś, Teoria automatów i języków formalnych, AOW EXIT, Warszawa 2005
2. J.E.Hopcroft, J.D.Ulman, Introduction to automata theory, languages and computing, Addison-Wesley, 1979
3. J.Gruska, Foundations of computing, Thompson, 1997
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

• [[ZASD Moduł 1|]] 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)