Jazyky a automaty

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra matematiky

Anotace:

Různé typy generativních gramatik a jim odpovídající automaty. S nimi spojené uzávěrové vlastnosti a algoritmické problémy.

Požadavky:

Osnova přednášek:

Generativní gramatiky, Chomského klasifikace, jazyky typu 0 a rozeznávací Turingovy stroje, kontextové jazyky a lineárně omezené automaty, bezkontextové jazyky a zásobníkové automaty, jazyky typu 3, konečné automaty a regulární jazyky, uzávěrové vlastnosti a algoritmické problémy.

Osnova cvičení:

Cíle studia:

Znalosti:

Seznámit studenty s klasickými výsledky teorie formálních jazyků, generativních gramatik a rozeznávacích automatů.

Schopnosti:

Orientovat se ve světě finitních popisů formálních jazyků a jejich využití v praxi.

Studijní materiály:

Povinná literatura:

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

Doporučená literatura:

[2] M. Demlová, V. Koubek: Algebraická teorie automatů, SNTL, Praha, 1990.

[3] M. Chytil: Automaty a gramatiky. SNTL, Praha 1984.

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