Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2024/2025

Jazyky, automaty a vyčíslitelnost

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
01JAVY Z,ZK 5 3+1 česky
Garant předmětu:
Přednášející:
Cvičící:
Předmět zajišťuje:
katedra matematiky
Anotace:

Konečné automaty a regulární jazyky, bezkontextové jazyky a zásobníkové automaty, jazyky typu 0 a Turingovy stroje. Algoritmy a algoritmicky vyčíslitelné funkce. Rekurzívní funkce, rekurzívní a rekurzívně spočetné množiny. Algoritmicky neřešitelné problémy.

Požadavky:
Osnova přednášek:

1. Konečné autoamaty, 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)

Osnova cvičení:

1. Kontrukce konečných automatů, použití vět o vkládání

2. Normalizované a standardní automaty, regulární operace

3. Přechod automat->regulární výraz: MNY algoritmus, BMC algoritmus, Ardenovo lemma

4. Determinizace a minimalizace konečného automatu

5. Konstrukce zásobníkových automatů, přechod zásobníkový automat - bezkontexrtová gramatika a zpět

6. Konstrukce turingových strojů, redukce nerozhodnutelných problémů

Cíle studia:

Znalosti:

Klasické výsledky teorie formálních jazyků, generativních gramatik a rozeznávacích automatů. Teorie rekurze jakožto matematické precizace intuitivního pojmu algoritmu a používané finitní a konstruktivní metody.

Schopnosti:

Orientace se ve světě finitních popisů formálních jazyků, funkcí a množin a jejich využití v praxi.

Studijní materiály:

Povinná literatura:

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

[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] 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.

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ů:
Platnost dat k 11. 11. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet5358406.html