UIN1005 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í
prof. RNDr. Alice Kelemenová, CSc. (přednášejí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ě
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
předmět má 11 mateřských oborů, zobrazit
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 1994, léto 1995, léto 1996, léto 1997, léto 1998, léto 1999, léto 2000, léto 2001, léto 2002, léto 2004, léto 2006, léto 2007, léto 2008, léto 2009, léto 2010, léto 2012, léto 2013.