UIBUC56 Theory of languages and automata I

Faculty of Philosophy and Science in Opava
Summer 2015
Extent and Intensity
2/2/0. 5 credit(s). Type of Completion: zk (examination).
Teacher(s)
prof. RNDr. Alice Kelemenová, CSc. (lecturer)
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
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.
Language of instruction
Czech
Further Comments
The course can also be completed outside the examination period.
Teacher's information
Credits from the exercises. Written exam.
The course is also listed under the following terms Summer 2012, Summer 2013, Summer 2014, Summer 2016, Summer 2017, Summer 2018, Summer 2019, Summer 2020, Summer 2021, Summer 2022.
  • Enrolment Statistics (Summer 2015, recent)
  • Permalink: https://is.slu.cz/course/fpf/summer2015/UIBUC56