The course is also offered to the students of the fields other than those the course is directly associated with.
Fields of study the course is directly associated with
there are 19 fields of study the course is directly associated with, display
Course objectives
At the end of the course students should be able to understand and explain the rich heritage of models and abstractions that have
arisen over the years, and to develop the students' capacity to form abstractions of their own and reason in terms of them.
Syllabus
Languages and grammars. Chomsky hierarchy.
Finite automata and regular grammars.
Properties of regular languages. Applications.
Context-free grammars and pushdown automata.
Properties of context-free languages.
Turing machines (TM). Computable languages and functions, LBA.
Properties of recursive and recursive enumerable languages.
Undecidability, halting problem for TM, Reduction, Post Correspondece Problem, undecidable problems from language theory.
GRUSKA, Jozef. Foundations of computing. London: International Thompson Computer Press, 1997. xv, 716 s. ISBN 1-85032-243-0. info
HOPCROFT, John E. and Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Reading: Addison-Wesley Publishing Company, 1979. 418 s., ob. ISBN 0-201-02988-X. info
CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984. 331 s. info
KOZEN, Dexter C. Automata and computability. New York: Springer, 1997. xiii, 400. ISBN 0387949070. info
SIPSER, Michael. Introduction to the theory of computation. 2nd ed. Boston: Thomson Course Technology, 2006. xix, 431. ISBN 0534950973. info
Teaching methods
Lectures, tutorials/exercises, and reading. Optional homeworks.
Assessment methods
Lectures and exercises. Optional homeworks. One midterm written exam and written final exam. Grading for the course: 20% midterm exam, 80% the final exam. Exams are written without any reading materials (closed book).