FPF:UIMOIBP009 TLA II - Course Information
UIMOIBP009 Theory of Languages and Automata II
Faculty of Philosophy and Science in OpavaWinter 2024
- Extent and Intensity
- 2/2/0. 5 credit(s). Type of Completion: zk (examination).
- Teacher(s)
- doc. RNDr. Lucie Ciencialová, Ph.D. (lecturer)
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 - Prerequisites
- 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.-2. Revision - finite automata and regular grammars. Language regularity criteria.
- 3.-4. Transformation of context-free grammars. Context-free criteria.
- 5.-7. Pushdown automata, variants, types of acceptance.
- 8. Closing properties of context-free languages.
- 9. Deterministic context-free languages.
- 10.-11. Grammars of type 0, Turing machines.
- 12. Grammars of type 1, Linear bounded automata.
- 13. Grammars and grammar systems not corresponding to the Chomsky hierarchy.
- 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
- Enrolment Statistics (Winter 2024, recent)
- Permalink: https://is.slu.cz/course/fpf/winter2024/UIMOIBP009