Počet kreditů 6
Vyučováno v Zimní
Rozsah výuky 2P+2S
Garant předmětu
Přednášející
Cvičící

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. 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.

Nejsou.

Cílem studia je seznámit studenty se základy teorie formálních jazyků. Hlavními prostředky studia jsou konečné automaty a gramatiky.

  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.

  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.

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

Rozvrh předmětu
Po
Út
St
Čt
PřednáškyCvičení