FPF:UIMOIBP009 TLA II - Course Information
UIMOIBP009 Theory of Languages and Automata II
Faculty of Philosophy and Science in OpavaWinter 2020
- Extent and Intensity
- 2/2/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:
- Prerequisites
- TYP_STUDIA(B)
The topics require some preliminary knowledge, so it is necessary for each student to familiarize themselves with the content of the course Theory of Languages and Automata I. - 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
- Information and communication technologies (programme FPF, MOI)
- Course objectives
- Basic theorems of the classical formal language theory. We put emphasis to basic algorithms and proof techniques.
- Learning outcomes
- Students will be able to: - define important concepts of theoretical computer science - using abstract computational models - apply the acquired knowledge on concrete examples.
- Syllabus
- 1. Revision - finite automata and regular grammars. Language regularity criteria.
- 2. Transformation of context-free grammars. Context-free criteria.
- 3. Pushdown automata, variants, types of acceptance.
- 4. Closing properties of context-free languages.
- 5. Deterministic context-free languages.
- 6. Grammars of type 0, Turing machines.
- 7. Grammars of type 1, Linear bounded automata.
- 8. Grammars and grammar systems not corresponding to the Chomsky hierarchy.
- Literature
- required literature
- 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.
- recommended literature
- MEDUNA, A. Automata and Languages: Theory and Applications. Springer, London, 2000. info
- ČERNÁ, I, M KŘETÍNSKÝ and 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
- Teaching methods
- Interactive lecture
Lecture supplemented with a discussion
Tutorials - Assessment methods
- Credit: two tests, attendance at seminars min. 75%. Exam: written and oral part, list of possible questions on the teacher's website
- Language of instruction
- Czech
- Further Comments
- Study Materials
- Enrolment Statistics (Winter 2020, recent)
- Permalink: https://is.slu.cz/course/fpf/winter2020/UIMOIBP009