Topic outline

  • A8B01DMG - Diskrétní matematika a grafy

    Základní pojmy teorie konečných automatů a gramatik: deterministické a nedeterministické konečné automaty, charakterizace třídy jazyků přijímaných konečným automatem a jejich popis regulárním výrazem. Gramatiky a jazyky generované danými gramatikami s důrazem na bezkontextové gramatiky. Vztah bezkontextových gramatik a zásobníkových automatů. Pojem Turingova stroje a seznámení studentů s tím, že existují algoritmicky nerozhodnutelné problémy.

  • Přednášky

    1. Abeceda, slova nad abecedou, zřetězení slov, jazyk.
    2. Deterministický konečný automat, stavový diagram.
    3. Jazyk přijímaný konečným automatem, Nerodova věta.
    4. Nedeterministické konečné automaty.
    5. Ekvivalence deterministických a nedeterministických konečných automatů.
    6. Regulární výrazy a regulární jazyky, Kleeneova věta.
    7. Algoritmická složitost úloh souvisejících s regulárními jazyky
    8. Gramatiky, regulární gramatiky a bezkontextové gramatiky, bezkontextové jazyky.
    9. Zásobníkové automaty a jejich vztah k bezkontextovým jazykům.
    10. Vlastnosti bezkontextových gramatik, lemma o vkládání. Uzavřenost třídy bezkontextových jazyků.
    11. Algoritmy pro řešení některých úloh pro bezkontextové jazyky.
    12. Turingovy stroje.
    13. Algoritmicky neřešitelné úlohy.
    14. Rezerva.

    • Cvičení

      1. Abeceda, slova nad abecedou, zřetězení slov, jazyk.
      2. Deterministický konečný automat, stavový diagram.
      3. Jazyk přijímaný konečným automatem, Nerodova věta.
      4. Nedeterministické konečné automaty.
      5. Ekvivalence deterministických a nedeterministických konečných automatů.
      6. Regulární výrazy a regulární jazyky, Kleeneova věta.
      7. Algoritmická složitost úloh souvisejících s regulárními jazyky.
      8. Gramatiky, regulární gramatiky a bezkontextové gramatiky, bezkontextové jazyky.
      9. Zásobníkové automaty a jejich vztah k bezkontextovým jazykům.
      10. Vlastnosti bezkontextových gramatik, lemma o vkládání. Uzavřenost třídy bezkontextových jazyků.
      11. Algoritmy pro řešení některých úloh pro bezkontextové jazyky, algoritmus CYK.
      12. Turingovy stroje.
      13. Algoritmicky neřešitelné úlohy.

      • Úkoly

        • Literatura

          [1] J.E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation, Second Edition, Addison-Wesley, 2001