UINK115 Theory of languages and automata I

Faculty of Philosophy and Science in Opava
Summer 2014
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)
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
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.
Literature
    required literature
  • VAVREČKOVÁ, Š. Prezentace (presentations). URL info
    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
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.
ActivityDifficulty [h]
Příprava na zápočet12
Účast na výuce12
Summary24
The course is also listed under the following terms Summer 2012, Summer 2013, Summer 2015, Summer 2016, Summer 2017, Summer 2018, Summer 2019, Summer 2020, Summer 2021, Summer 2022, Summer 2023.
  • Enrolment Statistics (Summer 2014, recent)
  • Permalink: https://is.slu.cz/course/fpf/summer2014/UINK115