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
01JAV Z,ZK 4 3+1 Czech
Garant předmětu:
Lecturer:
Tutor:
Supervisor:
Department of Mathematics
Synopsis:

Finite automata and regular languages. Context free languages and pushdown automata. Unrestricted languages and Turing machines. Algorithms a algorithmically enumerable functions. Recursive functions, recursive sets and recursively enumerable sets. Algorithmically unsolvable problems.

Requirements:
Syllabus of lectures:

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 (1 lecture)

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 (1 lecture)

Syllabus of tutorials:

1. Constructions of finite automata, use of star lemmas

2. Normalized and standard automata, regular operations

3. Conversion automata-&gt;regular expression: MNY algorithm, BMC algorithm, Arden lemma

4. Determinisation a minimisation of finite automata

5. Construction of pushdown automata, convesion pushdown automata-&gt;context-free grammar and vice versa

6. Construction of Turing machines, reduction of undecidable problems

Study Objective:

Acquired knowledge:

Classical results of theory of formal languages, grammars and automata. Recursion theory as a mathematically rigorous definition of intuitive notion of the algorithm, used finite and constructive methods.

Acquired skills:

Orientation in the field of formal languages, finite descriptions of functions and set. Practical applications.

Study materials:

Compulsory literature:

[1] J. Mareš: Jazyky, gramatiky a automaty. Vydavatelství ČVUT, Praha 2004.

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

Optional literature:

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

[2] J.E. Hopcroft, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation