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:

1/ Maximální povolený počet absencí na cvičení: 1

2/ Studující získá zápočet za předvedení řešení jedné (během domácí přípravy vypracované) úlohy na alespoň 5 ze 6 cvičení.

Osnova přednášek:

Osnova cvičení:

1. Konstrukce konečných automatů. Rozhodování neregularity jazyka pomocí vět o vkládání.

2. Hierarchie vět o vkládání. Kleenova věta.

3. Determinizace a minimalizace konečného automatu.

4. Konstrukce BKG. Speciální formy BKG.

5. Konstrukce zásobníkových automatů. Pumping lemma pro BKJ, uzávěrové vlasnosti třídy BKJ.

6.

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 2026/2027:

Rozvrh není připraven

Rozvrh na letní semestr 2026/2027:

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)