#
FI:IB005 Formal languages and Automata - Course Information

## IB005 Formal Languages and Automata

**Faculty of Informatics**

Spring 2022

**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).

Taught online. **Teacher(s)**- prof. RNDr. Mojmír Křetínský, CSc. (lecturer)

Marek Jankola (seminar tutor)

RNDr. David Klaška (seminar tutor)

Mgr. Juraj Major (seminar tutor)

Tereza Schwarzová (seminar tutor)

doc. RNDr. Jan Strejček, Ph.D. (seminar tutor)

Petra Hašková, DiS. (assistant)

Mgr. Miriama Jánošová (assistant)

Michael Koudela (assistant)

Bc. Anna Řechtáčková (assistant)

Patrícia Salajová (assistant)

Bc. Tereza Šťastná (assistant)

RNDr. Vladimír Štill, Ph.D. (assistant)

Mgr. Tatiana Zbončáková (assistant)

Pavol Žáčik (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 **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**- there are 56 fields of study the course is directly associated with, display
**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**- Č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. 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

- ČERNÁ, Ivana, Mojmír KŘETÍNSKÝ and Antonín KUČERA. Formální jazyky a automaty I.
**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).
**Language of instruction**- Czech
**Follow-Up Courses****Further Comments**- The course is taught annually.

The course is taught: every week. **Listed among pre-requisites of other courses****Teacher's information**- http://www.fi.muni.cz/usr/kretinsky/fja1.html

- Enrolment Statistics (Spring 2022, recent)
- Permalink: https://is.muni.cz/course/fi/spring2022/IB005