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

Harmonogram:

Výukové týdny: 2.10.2017 - 14.1.2018

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:

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

Cvičení - Cvičení.

Zkoušky - Organizace zkoušek.