UIIABP0012 Theory of languages and automata II

Faculty of Philosophy and Science in Opava
Winter 2020
Extent and Intensity
0/0/0. 5 credit(s). Type of Completion: zk (examination).
Teacher(s)
doc. RNDr. Lucie Ciencialová, Ph.D. (lecturer)
doc. RNDr. Lucie Ciencialová, Ph.D. (seminar tutor)
Mgr. Ondřej Mazurek (seminar tutor)
Guaranteed by
doc. RNDr. Lucie Ciencialová, Ph.D.
Institute of Computer Science – Faculty of Philosophy and Science in Opava
Timetable
Tue 15:35–17:09 B3b
  • Timetable of Seminar Groups:
UIIABP0012/A: Thu 9:45–11:19 B3b, O. Mazurek
Prerequisites (in Czech)
TYP_STUDIA ( B )
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
Course objectives (in Czech)
Od základů 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. Obsahová náplň cvičení vychází a časově sleduje obsahovou náplň přednášky.
Syllabus (in Czech)
  • 1. Opakování – konečné automaty a regulární gramatiky. Kritéria regulárnosti jazyka.
  • 2. Transformace bezkontextových gramatik.
  • 3. Kritéria bezkontextovosti.
  • 4. Zásobníkové automaty, varianty, typy akceptování.
  • 5. Uzávěrové vlastnosti bezkontextových jazyků.
  • 6. Deterministické bezkontextové jazyky.
  • 7. Gramatiky typu 0, Turingovy stroje.
  • 8. Gramatiky typu 1, Lineárně ohraničené automaty.
  • 9. Gramatiky a gramatické systémy neodpovídající Chomského hierarchii.
Literature
    required literature
  • VAVREČKOVÁ, Šárka. Teorie jazyků a automatů II. Opava: Slezská univerzita v Opavě, 2017
  • CIENCIALOVÁ, Lucie. Teoretické základy informatiky. Opava: Slezská univerzita v Opavě, 2014. ISBN 978-80-7510-130-3. info
    recommended literature
  • HOPCROFT, JOHN E, Rajeev MOTWANI and JEFFREY D ULLMAN. Introduction to automata theory, languages, and computation. Harlow: Pearson Addison-Wesley, 2014. ISBN 978-1-292-03905-3. info
  • ČERNÁ, I, M KŘETÍNSKÝ and A KUČERA. Automaty a formální jazyky I. Brno: FI MU, 2002. info
  • MEDUNA, A. Automata and Languages: Theory and Applications. Springer, London, 2000. info
  • 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
  • CHYTIL, M. Automaty a gramatiky. Praha: SNTL, 1984. info
Teaching methods
Lecture, tutorial
Assessment methods (in Czech)
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.
Language of instruction
Czech
The course is also listed under the following terms Winter 2021, Winter 2022, Winter 2023.
  • Enrolment Statistics (Winter 2020, recent)
  • Permalink: https://is.slu.cz/course/fpf/winter2020/UIIABP0012