Languages, Automata and Computability
| Code | Completion | Credits | Range | Language |
|---|---|---|---|---|
| 01JAU | Z,ZK | 4 | 3P+1C | Czech |
- Course guarantor:
- 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 2024/2025:
-
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon Tue Wed Thu Fri - Time-table for summer semester 2024/2025:
- Time-table is not available yet
- The course is a part of the following study plans:
-
- Matematická informatika (compulsory course in the program)