N_AG Automaty a gramatiky

Vysoká škola finanční a správní
zima 2015
Rozsah
2/1. 12 hodin KS/semestr. 6 kr. Ukončení: zk.
Vyučující
RNDr. Michal Žemlička, Ph.D. (cvičící)
RNDr. Petr Tesař, Ph.D. (pomocník)
Garance
RNDr. Michal Žemlička, Ph.D.
Katedra informatiky a matematiky (FES, KIM) – Katedry – Vysoká škola finanční a správní
Kontaktní osoba: Ing. Barbora Ptáčková
Rozvrh seminárních/paralelních skupin
N_AG/vAPH: So 24. 10. 11:30–13:00 S11, 14:00–15:30 S14, So 7. 11. 14:00–15:30 S11, So 5. 12. 9:45–11:15 S11, 11:30–13:00 S11, So 9. 1. 11:30–13:00 E227, M. Žemlička
Omezení zápisu do předmětu
Předmět je otevřen studentům libovolného oboru.
Cíle předmětu
Na konci tohoto kurzu bude student schopen používat automaty (zejména konečné a zásobníkové) a gramatiky jako formální prostředky popisu jazyka či chování softwaru, případně k modelování chování softwar, resp. jeho částí. Znalosti a dovednosti nabyté v tomto předmětu mu v mnoha případech umožní rozpoznat obtížnost úlohy a vyhledat vhodné nástroje.
Osnova
  • 1) úvod, pojmy, značení
  • 2) automaty, gramatiky, formální jazyky a jak to spolu souvisí
  • 3) konečné automaty, nedeterministické i deterministické
  • 4) regulární jazyky, regulární gramatiky
  • 5) bezkontextové gramatiky, bezkontextové jazyky
  • 6) zásobníkové automaty
  • 7) deteministické bezkontextové jazyky, LL a LR analýza
  • 8) kontextové jazyky, kontextové gramatiky, příklady
  • 9) obecné jazyky, Turingův stroj
  • 10) translátory
  • 11) jazyky, automaty a složitost
  • 12) ukázka použití nástrojů (flex, bizon, ...)
Literatura
    povinná literatura
  • M. Chytil: Automaty a gramatiky, Praha, SNTL, 1984
Výukové metody
Teoretická příprava, příklady, používání nástrojů.
Metody hodnocení
Psaný test s několika příklady a teoretickými problémy k řešení.
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 2016, zima 2017, zima 2018, zima 2019, zima 2020, zima 2021, zima 2022, zima 2023, zima 2024.