Languages, automata, and computability

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->regular expression: MNY algorithm, BMC algorithm, Arden lemma

4. Determinisation a minimisation of finite automata

5. Construction of pushdown automata, convesion pushdown automata->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

(1st ed.). Addison-Wesley 1979.

[3] 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:

• Aplikace softwarového inženýrství (elective course)