UINK106 Teorie jazyků a automatů II

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

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

Rozsah
6 hod/sem. 6 kr. Ukončení: zk.
Vyučující
doc. RNDr. Lucie Ciencialová, Ph.D. (přednášející)
doc. RNDr. Lucie Ciencialová, Ph.D. (cvičící)
Garance
doc. RNDr. Lucie Ciencialová, Ph.D.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě
Předpoklady
! UIN1006 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]
Příprava na zápočet 12
Příprava na zkoušku 12
Celkem 24
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 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.