UIN1006 Teorie jazyků a automatů II

Filozoficko-přírodovědecká fakulta v Opavě
zima 2023

Předmět se v období zima 2023 nevypisuje.

Rozsah
2/2/0. 6 kr. Ukončení: zk.
Vyučující
doc. RNDr. Lucie Ciencialová, Ph.D. (přednášející)
RNDr. Radka Poláková, Ph.D. (cvičící)
Garance
doc. RNDr. Lucie Ciencialová, Ph.D.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě
Předpoklady
! UINK106 Teorie jazyků a automatů II
Probíraná témata vyžadují jisté předběžné znalosti, proto je třeba aby sevkaždý student předem obeznámil s obsahem kurzu 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
Přecházíme ke složitějším teoretickým modelům struktur a postupů, tedy zásobníkovým automatům, Turingovým strojům a složitějším formám gramatik. Ke konci kurzu se studenti seznámí také s paralelními systémy včetně jejich praktického použití. Obsahová náplň cvičení vychází a časově sleduje obsahovou náplň přednášky.
Výstupy z učení
Student bude po absolvování předmětu schopen: - definovat důležité pojmy teoretické informatiky - používat abstraktní výpočetní modely - aplikovat získané poznatky na konkrétních příkladech.
Osnova
  • 1. Opakování – konečné automaty a regulární gramatiky. Kritéria regulárnosti jazyka.
  • 2. Transformace bezkontextových gramatik. Kritéria bezkontextovosti.
  • 3. Zásobníkové automaty, varianty, typy akceptování.
  • 4. Uzávěrové vlastnosti bezkontextových jazyků.
  • 5. Deterministické bezkontextové jazyky.
  • 6. Gramatiky typu 0, Turingovy stroje.
  • 7. Gramatiky typu 1, Lineárně ohraničené automaty.
  • 8. Gramatiky a gramatické systémy neodpovídající Chomského hierarchii.
Literatura
    povinná literatura
  • CIENCIALOVÁ, Lucie. Teoretické základy informatiky. Opava: Slezská univerzita v Opavě, 2014. ISBN 978-80-7510-130-3. info
  • VAVREČKOVÁ, Šárka. Teorie jazyků a automatů II. Opava: Slezská univerzita v Opavě, 2017.
    doporučená literatura
  • MEDUNA, A. Automata and Languages: Theory and Applications. Springer, London, 2000. info
  • ČERNÁ, I, M KŘETÍNSKÝ a A KUČERA. Automaty a formální jazyky I. Brno: FI MU, 2002. info
  • DEMLOVÁ, M. - KOUBEK, V. Algebraická teorie automatů. Praha: SNTL, 1990. info
  • CHYTIL, M. Automaty a gramatiky. Praha: SNTL, 1984. info
  • GRUSKA, J. Foundations of Computing. London: International Thomson Computer Press, 1997. 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., Motwani, R., Ullman, J. D. Introduction to Automata Theory, Languages and Computation. Upper Saddle River: Pearson Education Inc.,, 2003. info
Výukové metody
Přednáška s aktivizací
Přednáška s diskusí
Cvičení
Metody hodnocení
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 je na webu vyučujícího.
Informace učitele
Aktivity Náročnost [h]
Cvičení 20
Konzultace 5
Přednáška 20
Příprava na zápočet 20
Příprava na zkoušku 20
Celkem 85
Další komentáře
Studijní materiály
Předmět je dovoleno ukončit i mimo zkouškové období.
Předmět je zařazen také v obdobích zima 1993, zima 1994, zima 1995, zima 1996, zima 1997, zima 1998, zima 1999, zima 2003, zima 2004, zima 2005, zima 2006, zima 2007, zima 2008, zima 2009, zima 2010, zima 2011, zima 2012, zima 2013, zima 2014, zima 2015, zima 2016, zima 2017, zima 2018, zima 2019, zima 2020, zima 2021, zima 2022.