IB005 Formal Languages and Automata I

Faculty of Informatics
Spring 2011
Extent and Intensity
4/2. 6 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
prof. RNDr. Jiří Barnat, Ph.D. (seminar tutor)
prof. RNDr. Jan Strejček, Ph.D. (seminar tutor)
RNDr. Nikola Beneš, Ph.D. (seminar tutor)
RNDr. Jana Tůmová, Ph.D. (assistant)
Mgr. Bc. Tomáš Janík (seminar tutor)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.
Timetable
Wed 10:00–11:50 D2, Thu 14:00–15:50 D1
  • Timetable of Seminar Groups:
IB005/A: Thu 12:00–13:50 B411, J. Strejček
IB005/01: Mon 12:00–13:50 C511, J. Barnat
IB005/02: Thu 12:00–13:50 C511, J. Barnat
IB005/03: Wed 16:00–17:50 B204, J. Strejček
Prerequisites
MB005 Foundations of mathematics && ! IB102 Automata and Grammars
Knowlegde corresponding to the courses IB005 Induction and recursion MB005 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
there are 22 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. Computable languages and functions, LBA. Properties of recursive and recursive enumerable languages.
  • Deterministic pushdown automata. Properties and applications.
Literature
  • ČERNÁ, Ivana, Mojmír KŘETÍNSKÝ and Antonín KUČERA. Formální jazyky a automaty I. Elportál. Brno: Masarykova univerzita, 2006. ISSN 1802-128X. URL info
  • 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
  • SIPSER, Michael. Introduction to the theory of computation. 2nd ed. Boston: Thomson Course Technology, 2006, xix, 431. ISBN 0534950973. info
Teaching methods
Lectures, exercises, and reading. Optional homeworks.
Assessment methods
Lectures and exercises. Optional homeworks. Two midterm written exams and written final exam. Grading for the course: 15% each midterm exam, 70% the final exam. Exams are written without any reading materials (closed book).
Language of instruction
Czech
Follow-Up Courses
Further Comments
Study Materials
The course is taught annually.
Listed among pre-requisites of other courses
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja1.html
The course is also listed under the following terms Spring 2003, Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Spring 2020, Spring 2021, Spring 2022, Spring 2023, Spring 2024, Spring 2025.
  • Enrolment Statistics (Spring 2011, recent)
  • Permalink: https://is.muni.cz/course/fi/spring2011/IB005