Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2024/2025

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:
Data valid to 2024-05-28
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet6361806.html