FPF:UINK106 Theory of languages and automa - Course Information
UINK106 Theory of languages and automata II
Faculty of Philosophy and Science in OpavaWinter 2017
- Extent and Intensity
- 2/2/0. 6 credit(s). Type of Completion: zk (examination).
- Teacher(s)
- prof. RNDr. Alice Kelemenová, CSc. (lecturer)
RNDr. Šárka Vavrečková, Ph.D. (lecturer)
prof. RNDr. Alice Kelemenová, CSc. (seminar tutor)
RNDr. Šárka Vavrečková, Ph.D. (seminar tutor) - Guaranteed by
- prof. RNDr. Alice Kelemenová, CSc.
Institute of Computer Science – Faculty of Philosophy and Science in Opava - Prerequisites (in Czech)
- ( UINK105 Theory of Languages and Automa || UINK115 Theory of languages and automa || UIN1105 Theory of languages and automa ) && ( UIAI012 The Basic of Theoret. Comp. Sc || UIAI212 The Basis of Theoretical Compu || UIBUC56 Theory of languages and automa || UINK115 Theory of languages and automa || UIN1105 Theory of languages and automa )
Probíraná témata vyžadují jisté předběžné znalosti, proto je třeba aby každý student předem absolvoval buď Teorii jazyků a automatů I, nebo Základy teoretické informatiky 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
- Computer Science and Technology (programme FPF, B1801 Inf)
- Course objectives
- Basic theorems of the classical formal language theory. We put emphasis to basic algorithms and proof techniques.
- Syllabus
- Transformation of context-free grammars.
Test criteria for context-free languages.
Pushdown automata, variants, acceptance types.
Closure properties of context-free languages.
Deterministic context-free languages.
Grammars of type 0, Turing machines.
Grammars of type 1, Linearly Bounded Automata.
Chomski hierarchy - summary.
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.
- Transformation of context-free grammars.
- Literature
- recommended literature
- MEDUNA, A. Automata and Languages: Theory and Applications. Springer, London, 2000. 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. - ULLMAN, J. D. Teória jazykov a automatov. Bratislava: Alfa, 1987. info
- WOOD, D. Theory of computation. New York: John Wiley & Sons, 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.
- Teacher's information
- Credits from the exercises. Written exam - algorithms, oral exam - proofs of theorems.
Activity Difficulty [h] Příprava na zápočet 12 Příprava na zkoušku 12 Summary 24
- Enrolment Statistics (Winter 2017, recent)
- Permalink: https://is.slu.cz/course/fpf/winter2017/UINK106