Informace o předmětu (sylabus, systém hodnocení,...)

Literatura a jiné informační zdroje

1. týden: Formální jazyky. Gramatiky. Chomského hierarchie.

2. týden: Konečné automaty. Paralelní kompozice automatů.

3. týden: Věta o vkládání. Myhillova-Nerodova věta. Aplikace.

4. týden: Minimalizace konečných automatů. Nedeterministické konečné automaty.

6. týden: Vztah konečných automatů, regulárních výrazů a gramatik. Rozhodnutelné problémy pro regulární jazyky. Aplikace.

7. týden: Bezkontextové jazyky. Derivační stromy. Redukované gramatiky.

8. týden: Jednoduchá pravidla a epsilon-pravidla. Chomského normální forma. Věta o vkládání pro bezkontextové jazyky.

9. týden: Přímá a nepřímá levá rekurze. Greibachové normální forma. Zásobníkové automaty.

10. týden: Zásobníkové automaty, metody akceptování. Rozšířené zásobníkové automaty.

11. týden: Zásobníkové automaty a bezkontextové gramatiky. Nedeterministická syntaktická analýza.

12. týden: Algoritmus Cocke-Younger-Kasami. Uzávěrové vlastnosti a (ne)rozhodnutelné problémy pro bezkontextové jazyky.

13. týden: Deterministické bezkontextové jazyky a jejich vlastnosti. Turingovy stroje.