I005 Formal Languages and Automata I

Faculty of Informatics
Spring 1999
Extent and Intensity
3/2. 5 credit(s). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
Guaranteed by
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.
Prerequisites
Recommended I000 Induction and Recursion and M005 Foundations of mathematics
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
Syllabus
  • Languages and grammars. Chomsky hierarchy.
  • Finite automata and regular grammars.
  • Properties of regular languages.
  • Context-free grammars and pushdown automata.
  • Properties of context-free languages.
  • Deterministic pushdown automata.
  • Turing machines. Computable languages and functions.
  • Undecidability, (semi)decidability. Halting problem for TM.
  • Post's correspondence problem. Undecidable CFL problems.
Literature
  • I.Černá, M.Křetínský, A.Kučera: FJA I, interní materiál FI MU
  • 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. URL info
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
Assessment methods (in Czech)
2 písemné zkoušky během semestru, kdy je povoleno použití vlastních materiálů (knihy, poznámky z přrnášek a cvičení). Závěrečná písemná zkouška je bez povolení takových materiálů.
Language of instruction
Czech
Follow-Up Courses
Further Comments
The course is taught annually.
The course is taught: every week.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja1.html
The course is also listed under the following terms Spring 1995, Autumn 1995, Spring 1996, Spring 1997, Spring 1998, Spring 2000, Spring 2001, Spring 2002.
  • Enrolment Statistics (Spring 1999, recent)
  • Permalink: https://is.muni.cz/course/fi/spring1999/I005