N_AG Automaty a gramatiky

Vysoká škola finanční a správní
zima 2025
Rozsah
2/1/0. 12 hodin KS/semestr. 6 kr. Ukončení: zk.
Garance
prof. RNDr. Ondřej Čepek, Ph.D.
Katedra informatiky a matematiky (FES, KIM) – Katedry – Vysoká škola finanční a správní
Kontaktní osoba: Ivana Plačková
Předpoklady
Nejsou vyžadovány žádné předpoklady.
Omezení zápisu do předmětu
Předmět je otevřen studentům libovolného oboru.
Cíle předmětu
Cílem studijního předmětu je seznámit studenty s problematikou konečných automatů (deterministických i nedeterministických) a jimi rozpoznávaných jazyků (tzv. regulárních jazyků). Bude též studována ekvivalence s regulárními gramatikami a regulárními výrazy.
Výstupy z učení
Na konci tohoto kurzu bude student schopen navrhovat konečné automaty (deterministické i nedeterministické) pro konkrétní jazyky. Bude schopen porozumět regulárnímu výrazu a také regulární výraz popisující konkrétní jazyk vytvořit. Dále bude umět přepsat konečný automat do systému pravidel, tedy do regulární gramatiky.
Osnova
  • 1. Deterministické konečné automaty (DFA) a regulární jazyky (REG) 2. Pumping lemma a jeho použití, Myhill-Nerodova věta a příklady neregulárních jazyků 3. Nedeterministické KA (NFA) a jejich ekvivalence s DFA 4. Regulární výrazy a Kleeneho věta 5. Regulární gramatiky 6. Algoritmy založené na DFA (Aho-Corasick a Knuth-Morris-Pratt)
Literatura
    doporučená literatura
  • Eliška Šestáková: Automaty a Gramatiky – Sbírka řešených příkladů (nakladatelství ČVUT 2020)
  • M. Chytil: Automaty a gramatiky, Praha, SNTL, 1984
Výukové metody
Výklad teorie, řešení příkladů.
Metody hodnocení
Předmět je zakončen písemnou zkouškou v trvání 60 minut.
Další komentáře
Předmět je dovoleno ukončit i mimo zkouškové období.
Předmět je zařazen také v obdobích zima 2014, zima 2015, zima 2016, zima 2017, zima 2018, zima 2019, zima 2020, zima 2021, zima 2022, zima 2023, zima 2024.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.vsfs.cz/predmet/vsfs/zima2025/N_AG