FPF:UINK115 Theory of languages and automa - Course Information
UINK115 Theory of languages and automata I
Faculty of Philosophy and Science in OpavaSummer 2016
- Extent and Intensity
- 0/0. 6 credit(s). Type of Completion: zk (examination).
- Teacher(s)
- prof. RNDr. Alice Kelemenová, CSc. (lecturer)
RNDr. Šárka Vavrečková, Ph.D. (lecturer) - Guaranteed by
- prof. RNDr. Alice Kelemenová, CSc.
Institute of Computer Science – Faculty of Philosophy and Science in Opava - 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
- Computer Science and Technology (programme FPF, B1801 Inf)
- Course objectives
- Basic notations of the theory and language representation by formal grammars and abstract machines
- Syllabus
- 1. Introduction to the formal language theory.
2. Formal language, basic operations and mappings.
3. Formal grammars, motivation, Sequential grammars, Chomsky hierarchy.
5. Typical grammars and languages of the Chomsky hierarchy.
6. Normal forms of grammars.
7. Finite automata.
8. Nondeterminism, nondeterministic finite automaton.
9. Pushdown automaton.
10.Turing machine.
11. Variants of TS and linear bounded automata.
Exercises follow the content of lectures.
Literature
Harrison, M. A.: Introduction to Formal Language Theory. Addison-Wesley P. C. 1978
Rozenberg, G., Salomaa, A. Eds.: Handbook of Formal Languages. Berlin: Springer, 1997.
Wood, D.: Theory of computation. New York: John Wiley & Sons, 1987.
- 1. Introduction to the formal language theory.
- Literature
- recommended literature
- 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
- HOPCROFT, J. E. - ULLMAN, J. D. Teória jazykov a automatov. Bratislava: Alfa, 1987. info
- CHYTIL, M. Automaty a gramatiky. Praha: SNTL, 1984. info
- Teaching methods
- Interactive lecture
Lecture supplemented with a discussion
Lecture with a video analysis - Assessment methods
- Written exam
Exam - Language of instruction
- Czech
- Further comments (probably available only in Czech)
- The course can also be completed outside the examination period.
Information on the extent and intensity of the course: Přednáška 6 HOD/SEM, Cvičení 6 HOD/SEM. - Teacher's information
- Credits from the exercises. Written exam.
Activity Difficulty [h] Příprava na zápočet 12 Účast na výuce 12 Summary 24
- Enrolment Statistics (Summer 2016, recent)
- Permalink: https://is.slu.cz/course/fpf/summer2016/UINK115