Jazyky, automaty a vyčíslitelnost

Garant předmětu:

Petr Ambrož

Přednášející:

Petr Ambrož

Cvičící:

Petr Ambrož

Předmět zajišťuje:

katedra matematiky

Anotace:

1. Konečné automaty, regulární jazyky a operace, věty o vkládání (3 přednášky)

2. Kleenova věta (2 přednášky)

3. Determinizace a minimalizace (2 přednášky)

4. Bezkontextové gramatiky a jejich redukce (2 přednášky)

5. Zásobníkové automaty a bezkontextové jazyky (2 přednášky)

6. Věta o vkládání pro bezkontextové jazyky, uzavřenost BKJ vůči operacím (2 přednášky)

7. Turingův stroj, rekurzivní a rekurzivně spočetné jazyky, metody návrhu Turingových strojů (2 přednášky)

8. Nerozhodnutelnost (1 přednáška)

9. Riceova věta, Postův korespondenční problém, nerozhodnutelné vlastnosti BKJ (2 přednášky)

Požadavky:

Osnova přednášek:

Osnova cvičení:

Cíle studia:

Studijní materiály:

Povinná literatura:

[1] J. Mareš: Jazyky, gramatiky a automaty (2. vydání). Vydavatelství ČVUT, Praha 2011.

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

Doporučená literatura:

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

[2] P. Linz: An Introduction to Formal Languages and Automata (6th ed.), Jones & Bartlett Learning 2016.

[3] J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation (3rd ed.), Pearson 2013.

Poznámka:

Rozvrh na zimní semestr 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
Po	místnost TR:205 Ambrož P. 14:00–15:50 (přednášková par. 1) Trojanova 13 učebna 205
Út	místnost TR:205 Ambrož P. 08:00–09:50 (přednášková par. 1) Trojanova 13 učebna 205
St
Čt
Pá

Rozvrh na letní semestr 2024/2025:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Matematická informatika (povinný předmět programu)