Languages, Automata and Computability

Garant předmětu:

Petr Ambrož

Lecturer:

Petr Ambrož

Tutor:

Petr Ambrož

Supervisor:

Department of Mathematics

Synopsis:

1. Finite automata, regular languages and operations, star lemmas. (3 lectures)

2. Kleene theorem (2 lectures)

3. Determinisation a minimisation (2 lectures)

4. Confext-free grammas and their reductions (2 lectures)

5. Pushdown automata and context-free languages (2 lectures)

6. Star lemma for CFL, closure properties of CFL (2 lectures)

7. Turing machine, recursive and recursively enumerable languages, methods of design of turing machines (2 lectures)

8. Undecidability (1 lecture)

9. Rice theorem, Post correspondence problem, undecidable properties of CFL (2 lectures)

Requirements:

Syllabus of lectures:

Syllabus of tutorials:

Study Objective:

Study materials:

Compulsory literature:

[1] J. Mareš: Jazyky, gramatiky a automaty (2. vydání). Vydavatelství ČVUT, Praha 2011.

[2] J. Mareš: Teorie vyčíslitelnosti. Vydavatelství ČVUT, Praha 2008.

[3] P. Linz: An Introduction to Formal Languages and Automata (6th ed.), Jones & Bartlett Learning 2016.

Optional literature:

[1] J. Sakarovitch: Elements of Automata Theory, Cambridge University Press 2009.

[2] J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation (3rd ed.). Pearson 2013.

Note:

Time-table for winter semester 2023/2024:

Time-table is not available yet

Time-table for summer semester 2023/2024:

Time-table is not available yet

The course is a part of the following study plans:

• Aplikace informatiky v přírodních vědách (elective course)
• Matematická informatika (compulsory course in the program)