UIN1105 Teorie jazyků a automatů I

Filozoficko-přírodovědecká fakulta v Opavě
léto 2013
Rozsah
2/2/0. 6 kr. Ukončení: zk.
Vyučující
prof. RNDr. Alice Kelemenová, CSc. (přednášející)
RNDr. Šárka Vavrečková, Ph.D. (přednášející)
Garance
prof. RNDr. Alice Kelemenová, CSc.
Ú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é jazyky, jejich varianty a vlastnosti.
    Normální formy bezkontextových jazyků.
    Pumping lemma pro bezkontextové jazyky.
Literatura
    povinná literatura
  • VAVREČKOVÁ, Š. Prezentace (presentations). 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
Informace učitele
AktivityNáročnost [h]
Příprava na zápočet12
Účast na výuce12
Celkem24
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 2014, léto 2015, léto 2016, léto 2017, léto 2018, léto 2019, léto 2020, léto 2021, léto 2022, léto 2023.