UIIABP0012 Theory of languages and automata II

Faculty of Philosophy and Science in Opava
Winter 2021
Extent and Intensity
0/0/0. 5 credit(s). Type of Completion: zk (examination).
Teacher(s)
doc. RNDr. Lucie Ciencialová, Ph.D. (lecturer)
Mgr. Ondřej Mazurek (seminar tutor)
RNDr. Radka Poláková, Ph.D. (seminar tutor)
Guaranteed by
doc. RNDr. Lucie Ciencialová, Ph.D.
Institute of Computer Science – Faculty of Philosophy and Science in Opava
Timetable
Tue 16:25–18:00 B4
  • Timetable of Seminar Groups:
UIIABP0012/A: Thu 8:05–9:40 B2, R. Poláková
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
Further Comments
Study Materials
The course is also listed under the following terms Winter 2020, Winter 2022, Winter 2023.
  • Enrolment Statistics (Winter 2021, recent)
  • Permalink: https://is.slu.cz/course/fpf/winter2021/UIIABP0012