Jazyky, automaty a vyčíslitelnost

Garant předmětu:

Přednášející:

Cvičící:

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:

Další informace:

Pro tento předmět se rozvrh nepřipravuje

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

• Aplikace informatiky v přírodních vědách (volitelný předmět)
• Matematická informatika (povinný předmět programu)