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

Teorie jazyků a automatů

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
XP01TJA ZK 4 2P+1S česky
Přednášející:
Cvičící:
Předmět zajišťuje:
katedra matematiky
Anotace:

Konečné automaty. Nerodova věta a její aplikace, redukce automatu. Nedeterministické automaty též s e-přechody. Regulární výrazy a Kleeneova věta. Gramatiky a jejich klasifikace. Bezkontextové gramatiky, jejich redukce. Zásobníkové automaty. Vztah mezi zásob. automaty a bezkontextovými gramatikami. Chomského normální tvar, lemma ovkládání. Algoritmus CYK pro bezkontextové gramatiky. Turingovy stroje jako akceptory a jako počítače funkcí. Nerozhodnutelnost problému zastavení Turingova stroje. Další algoritmicky neřešitelné úlohy.

Požadavky:
Osnova přednášek:
Osnova cvičení:
Cíle studia:
Studijní materiály:

1. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 2001.

Poznámka:

Předmět je nabízen jednou za dva roky.

Další informace:
http://math.feld.cvut.cz/demlova/teaching/tja.htm
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 14. 8. 2020
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet11506904.html