Výuka - předmět Jazyky, automaty a gramatiky, akad. rok 2019/20

Harmonogram:

Týdenní osnova:

1. Abeceda, slova nad abecedou, jazyk nad abecedou. Automaty s výstupem.
2. Deterministický konečný automat, redukce automatu. Regulární jazyky, lemma o vkládání pro regulární jazyky.
3. Nerodova věta. Uzavřenost třídy regulárních jazyků na množinové operace.
4. Nedeterministický konečný automat, ekvivalence deterministických a nedeterministických automatů.
5. Regulární výrazy. Kleeneova věta. Uzavřenost třídy jazyků na další operace.
6. Dvousměrné konečné automaty. Algoritmická řešitelnost problémů souvisejících s regulárními jazyky.
7. Gramatiky, bezkontextové gramatiky. Derivační strom a levá derivace pro bezkontextové gramatiky.
8. Regulární gramatiky a jejich vztak k regulárním jazykům. Redukce bezkontextových gramatik.
9. Bezkontextová gramatika v Chomského normálním tvaru, lemma o vkládání pro bezkontextové gramatiky.
10. Algoritmus CYK pro bezkontextové gramatiky v Chomského normálním tvaru. Algoritmická řešitelnost úloh pro bezkontextové jazyky.
11. Zásobníkové automaty a jejich vztah k bezkontextovým gramatikám.
12. Deterministické zásobníkové automaty a bezprefixové jazyky.
13. Turingovy stroje.
14. Rezerva.

Literatura:

• J.E. Hopcroft. R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages and Computation, Second Edition, Addison-Wesley, 2001.

Stručný obsah přednášek - Přednášky.

Cvičení - Cvičení.

Zkoušky - Organizace zkoušek.

Konzultační hodiny: úterý 11 - 12 hodin, Jugoslávských partyzánů 3, budova B, místnost 504.