UINK105 Teorie jazyků a automatů I

Filozoficko-přírodovědecká fakulta v Opavě
léto 2011
Rozsah
2/2/0. 4 kr. Ukončení: z.
Vyučující
RNDr. Šárka Vavrečková, Ph.D. (přednášející)
Garance
RNDr. Šárka Vavrečková, Ph.D.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě
Předpoklady
! UIN1005 Teorie jazyků a automatů I
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 2010.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.slu.cz/predmet/fpf/leto2011/UINK105