Topic outline

  • B4B01JAG, A4B01JAG - Jazyky, automaty a gramatiky

    Základní pojmy teorie konečných automatů a gramatik: deterministické a nedeterministické 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. Pojem zásobníkového automatu a jeho vztah k bezkontextovým gramatikám. Na závěr se studenti seznámí s pojmem Turingova stroje a 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 a jeho stavový diagram. Jazyk přijímaný konečným automatem. Regulární jazyky.
    3.   Lemma o vkládání a Nerodova věta. Redukce konečného automatu.
    4.   Nedeterministické konečné automaty. Podmnožinová konstrukce. Uzavřenost třídy jazyků přijímaných konečným automatem na sjednocení, zřetězení a Kleeneho operaci.
    5.   Regulární výrazy. Vztah regulárních jazyků a regulárních výrazů ? Kleeneho věta.
    6.   Algoritmická složitost úloh souvisejících s regulárními jazyky. Pojem gramatiky.
    7.   Chomského hierarchie tříd jazyků generovaných gramatikou. Regulární gramatiky a regulární jazyky. Bezkontextové gramatiky a bezkontextové jazyky.
    8.   Lemma o vkládání. Redukce bezkontextové gramatiky.
    9.   Zásobníkové automaty a jazyky přijímané zásobníkovými automaty prázdným zásobníkem a koncovým stavem.
    10.   Vlastnosti třídy bezkontextových jazyků.
    11.   Deterministické zásobníkové automaty a jejich vlastnosti. Třída deterministických jazyků a třída bezprefixových jazyků.
    12.   Seznámení sTuringovými stroji.
    13.   Krátké seznámení s nerozhodnutelnými jazyky a algoritmicky neřešitelnými úlohami.

    • Cvičení

      1.   Abeceda, slova nad abecedou, zřetězení slov, jazyk.
      2.   Deterministický konečný automat a jeho stavový diagram. Jazyk přijímaný konečným automatem. Regulární jazyky.
      3.   Lemma o vkládání a Nerodova věta. Redukce konečného automatu.
      4.   Nedeterministické konečné automaty. Podmnožinová konstrukce. Uzavřenost třídy jazyků přijímaných konečným automatem na sjednocení, zřetězení a Kleeneho operaci.
      5.   Regulární výrazy. Vztah regulárních jazyků a regulárních výrazů ? Kleeneho věta.
      6.   Algoritmická složitost úloh souvisejících s regulárními jazyky. Pojem gramatiky.
      7.   Chomského hierarchie tříd jazyků generovaných gramatikou. Regulární gramatiky a regulární jazyky. Bezkontextové gramatiky a bezkontextové jazyky.
      8.   Lemma o vkládání. Redukce bezkontextové gramatiky.
      9.   Zásobníkové automaty a jazyky přijímané zásobníkovými automaty prázdným zásobníkem a koncovým stavem.
      10.   Vlastnosti třídy bezkontextových jazyků.
      11.   Deterministické zásobníkové automaty a jejich vlastnosti. Třída deterministických jazyků a třída bezprefixových jazyků.
      12.   Seznámení sTuringovými stroji.
      13.   Krátké seznámení s nerozhodnutelnými jazyky a algoritmicky neřešitelnými úlohami.

      • Úkoly

        • Literatura

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