Jazyky, automaty a vyčíslitelnost

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 (1 přednáška)

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. (1 přednáška)

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ů:

• Aplikace softwarového inženýrství (volitelný předmět)