IB005 Formal Languages and Automata

Faculty of Informatics
Spring 2023
Extent and Intensity
2/2/1. 4 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)
Mgr. Paulína Ayaziová (seminar tutor)
Mgr. Tomáš Foltýnek, Ph.D. (seminar tutor)
Mgr. Marek Jankola (seminar tutor)
Bc. Tereza Kinská (seminar tutor)
RNDr. David Klaška (seminar tutor)
Mgr. Tomáš Macháček (seminar tutor)
Mgr. Juraj Major (seminar tutor)
Mgr. Tereza Schwarzová (seminar tutor)
prof. RNDr. Jan Strejček, Ph.D. (seminar tutor)
Bc. Adéla Štěpková (seminar tutor)
RNDr. Martin Jonáš, Ph.D. (assistant)
Mgr. Anna Řechtáčková (assistant)
prof. Dr. rer. nat. RNDr. Mgr. Bc. Jan Křetínský, Ph.D. (assistant)
Mgr. Michael Koudela (assistant)
Petra Ludvová Hašková, DiS. (assistant)
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.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Wed 15. 2. to Wed 10. 5. Wed 10:00–11:50 D1
  • Timetable of Seminar Groups:
IB005/A: Wed 15. 2. to Wed 10. 5. Wed 14:00–15:50 A320, D. Klaška
IB005/01: Thu 16. 2. to Thu 11. 5. Thu 12:00–13:50 A320, J. Strejček
IB005/02: Thu 16. 2. to Thu 11. 5. Thu 18:00–19:50 B410, T. Kinská
IB005/03: Thu 16. 2. to Thu 11. 5. Thu 16:00–17:50 B411, T. Foltýnek
IB005/04: Thu 16. 2. to Thu 11. 5. Thu 14:00–15:50 B411, T. Foltýnek
IB005/05: Wed 15. 2. to Wed 10. 5. Wed 18:00–19:50 A320, A. Štěpková
IB005/06: Tue 14. 2. to Tue 9. 5. Tue 14:00–15:50 A320, M. Jankola
Prerequisites
IB000 Math. Foundations of CS && ! IB102 Automata and Grammars
Knowlegde corresponding to the courses IB000 Mathematical Foundations of Computer Science
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
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.
Learning outcomes
At the end of the course students should be able to:
Demonstrate an in-depth understanding of theories, concepts and techniques in automata and their link to computation.
Develop abstract machines that demonstrate the properties of physical/SW systems and be able to specify the possible inputs, processes and outputs of these machines. Analyze the computational strengths and weaknesses of these machines.
Understand the concept of computability by manipulating these machines in order to demonstrate the properties of computational processes.
Practice techniques of program design and development by using abstract machines. Apply automata concepts and techniques in designing systems that address real world problems
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.
Literature
    not specified
  • HOPCROFT, John E., Rajeev MOTWANI and Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. 3rd ed. Boston: Pearson/Addison Wesley, 2007, xvii, 535. ISBN 0321455363. info
  • HOPCROFT, John E., Rajeev MOTWANI and Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Third edition. Harlow: Pearson, 2014, ii, 488. ISBN 9781292039053. 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
  • 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
  • CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
Teaching methods
Lectures, tutorials/exercises, reading, and homeworks.
Assessment methods
Final grading is based on homeworks and a written final exam closed book (without any reading materials).
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 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Spring 2020, Spring 2021, Spring 2022, Spring 2024, Spring 2025.
  • Enrolment Statistics (Spring 2023, recent)
  • Permalink: https://is.muni.cz/course/fi/spring2023/IB005