Course: The Basic of Theoretical Computer Science II

« Back
Course title The Basic of Theoretical Computer Science II
Course code UI/AI219
Organizational form of instruction Lecture
Level of course Bachelor
Year of study not specified
Semester Winter
Number of ECTS credits 7
Language of instruction Czech
Status of course Compulsory
Form of instruction Face-to-face
Work placements This is not an internship
Recommended optional programme components None
Course availability The course is available to visiting students
  • KELEMENOVÁ Alice, doc. RNDr. CSc.
  • VAVREČKOVÁ Šárka, RNDr. Ph.D.
Course content
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.

Learning activities and teaching methods
Interactive lecture, Lecture supplemented with a discussion, Lecture with a video analysis
  • unspecified - 6 hours per semester
  • unspecified - 20 hours per semester
  • unspecified - 20 hours per semester
  • unspecified - 9 hours per semester
  • unspecified - 30 hours per semester
Recommended literature
  • GRUSKA, J. Foundations of Computing. London: International Thomson Computer Press, 1997.
  • HOPCROFT, J. E. - ULLMAN, J. D. Teória jazykov a automatov. Bratislava: Alfa, 1987.
  • CHYTIL, M. Automaty a gramatiky. Praha: SNTL, 1984.
  • MEDUNA, A. Automata and Languages: Theory and Applications. Springer, London, 2000.
  • MEDUNA, A. MEDUNA, A. Gramatiky, automaty a kompilátory. Brno: VUT, 1987.
  • MOLNÁR, Ľ. ČEŠKA, M. , MELICHAR, B. Gramatiky a jazyky. Bratislava: ALFA, 1987.
  • WOOD, D. Theory of computation. New York: John Wiley & Sons, 1987.

Study plans that include the course
Faculty Study plan (Version) Branch of study Category Recommended year of study Recommended semester
Faculty of Philosophy and Science in Opava Applied Computer Science (1) Informatics courses 2 Winter