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

Languages, Automata and Computability

Login to KOS for course enrollment Display time-table
Code Completion Credits Range Language
01JAU Z,ZK 4 3P+1C Czech
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:
Data valid to 2024-07-20
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet6361806.html