Jazyky, automaty a vyčíslitelnost
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ů: