Languages, Automata and Computability

The course is not on the list Without time-table

Code	Completion	Credits	Range	Language
01JAU	Z,ZK	4	3P+1C	Czech

Garant předmětu:

Lecturer:

Tutor:

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:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans: