Výuka - předmět Jazyky, automaty a gramatiky, akad. rok 2022/23
Harmonogram:
| Výukové týdny: | 19.9.2022 - 15.1.2023 |
Týdenní osnova:
- Abeceda, slova nad abecedou, jazyk nad abecedou. Automaty s výstupem.
- Deterministický konečný automat, redukce automatu. Regulární jazyky, lemma o vkládání pro regulární jazyky.
- Nerodova věta. Uzavřenost třídy regulárních jazyků na množinové operace.
- Nedeterministický konečný automat, ekvivalence deterministických a nedeterministických automatů.
- Regulární výrazy. Kleeneova věta. Uzavřenost třídy jazyků na další operace.
- Dvousměrné konečné automaty. Algoritmická řešitelnost problémů souvisejících s regulárními jazyky.
- Gramatiky, bezkontextové gramatiky. Derivační strom a levá derivace pro bezkontextové gramatiky.
- Regulární gramatiky a jejich vztak k regulárním jazykům. Redukce bezkontextových gramatik.
- Bezkontextová gramatika v Chomského normálním tvaru, lemma o vkládání pro bezkontextové gramatiky.
- Algoritmus CYK pro bezkontextové gramatiky v Chomského normálním tvaru. Algoritmická řešitelnost úloh pro bezkontextové jazyky.
- Zásobníkové automaty a jejich vztah k bezkontextovým gramatikám.
- Deterministické zásobníkové automaty a bezprefixové jazyky.
- Turingovy stroje.
- 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.
Online konzultační hodiny budou upřesněny