Teorie jazyků a automatů

Přednášející:

Marie Demlová

Cvičící:

Marie Demlová

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.

Rozvrh na zimní semestr 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 2011/2012:

Rozvrh není připraven

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)