Teorie jazyků a automatů

Garant předmětu:

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

• Doktorské studium, prezenční forma (povinně volitelný předmět)
• Doktorské studium, kombinovaná forma (povinně volitelný předmět)
• Doktorské studium, strukturované prezenční (povinně volitelný předmět)
• Doktorské studium, strukturované kombinované (povinně volitelný předmět)