UIN1105 Teorie jazyků a automatů I

Filozoficko-přírodovědecká fakulta v Opavě
léto 2018
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í)
Mgr. Jan Drastik, Ph.D. (cvičící)
prof. RNDr. Alice Kelemenová, CSc. (cvičící)
RNDr. Šárka Vavrečková, Ph.D. (cvičí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é 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]
Cvičení20
Přednáška20
Příprava na zápočet15
Příprava na zkoušku15
Celkem70
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 2019, léto 2020, léto 2021, léto 2022, léto 2023.