UINK115 Teorie jazyků a automatů I

Filozoficko-přírodovědecká fakulta v Opavě
léto 2021
Rozsah
6/6/0. Přednáška 6 HOD/SEM, Cvičení 6 HOD/SEM. 6 kr. Ukončení: zk.
Vyučující
doc. RNDr. Lucie Ciencialová, Ph.D. (přednášející)
doc. RNDr. Lucie Ciencialová, Ph.D. (cvičící)
Garance
doc. RNDr. Lucie Ciencialová, Ph.D.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Cíle předmětu
V tomto kurzu se zabýváme především teoretickými základy metod požívaných pro modelování struktur a postupů, tedy konečnými automaty, regulárními jazyky, regulárními výrazy a bezkontextovými gramatikami. Na teoretický základ navazují také příklady využití v praxi. Obsahová náplň cvičení vychází a časově sleduje obsahovou náplň přednášek.
Osnova
  • Abeceda, formální jazyky, operace s formálními jazyky.
    Konečný automat.
    Regulární jazyky, Pumping lemma pro regulární jazyky, regulární výrazy, regulární gramatiky.
    Uzávěrové vlastnosti regulárních jazyků.
    Chomského hierarchie jazyků.
    Bezkontextové gramatiky, jejich varianty a vlastnosti.
Literatura
    povinná literatura
  • Vavrečková, Šárka. WWW stránky předmětu, skripta. URL info
    doporučená literatura
  • GRUSKA, J. Foundations of Computing. London: International Thomson Computer Press, 1997. info
  • DEMLOVÁ, M. - KOUBEK, V. Algebraická teorie automatů. Praha: SNTL, 1990. info
  • MOLNÁR, Ľ. - ČEŠKA, M. - MELICHAR, B. Gramatiky a jazyky. Bratislava: Alfa, 1987. info
  • MEDUNA, A. MEDUNA, A. Gramatiky, automaty a kompilátory. Brno: VUT, 1987. info
  • HOPCROFT, J. E. - ULLMAN, J. D. Teória jazykov a automatov. Bratislava: Alfa, 1987. info
  • CHYTIL, M. Automaty a gramatiky. Praha: SNTL, 1984. info
Výukové metody
Přednáška s aktivizací
Přednáška s diskusí
Přednáška s analýzou videozáznamu
Metody hodnocení
Písemná zkouška
Zkouška
Informace učitele
Teoretické a praktické zvládnutí témat předmětu.
Zápočet: dvě písemky, účast na cvičeních min. 75 %.
Zkouška: písemná a ústní část, seznam možných otázek na webu vyučujícího.
AktivityNáročnost [h]
Domácí příprava na výuku30
Přednáška6
Příprava na zápočet20
Příprava na zkoušku20
Celkem76
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 léto 2012, léto 2013, léto 2014, léto 2015, léto 2016, léto 2017, léto 2018, léto 2019, léto 2020, léto 2022, léto 2023.