Automaty a gramatiky - cvičení

Letní semestr 2024/25 (LS 2022/23)

Rozvrh: čtvrtek od 12:20 v S7
Vyučující: Petr Gregor (gregor(at)ktiml.mff.cuni.cz)
Informace o přednášce: 2/2 Zk/Z NTIN071 v SISu, na stránce k přednášce

Procvičované příklady

  • Cvičení 1 - 20. 2.: Konečné automaty. Myhill-Nerodova věta.
  • Cvičení 2 - 27. 2.: Pumping lemma. Homomorfismus automatů.
  • Cvičení 3 - 6. 3.: Stavová ekvivalence, podílové automaty, redukce automatů. Nedeterministické konečné automaty.
  • Cvičení 4 - 13. 3.: Uzávěrové vlastnosti třídy regulárních jazyků. Řetězcové operace s jazyky.
  • Cvičení 5 - 20. 3.: Kleeneho věta, regulární výrazy, převody regulárního výrazu na automat a zpátky.
  • Cvičení 6 - 27. 3.: Dvoucestné automaty. Gramatiky.
  • Cvičení 7 - 3. 4.: Pravé lineární a bezkontextové gramatiky.
  • Cvičení 8 - 10. 4.: Redukce gramatiky, Chomského normální tvar. Pumping lemma pro BKJ.
  • Cvičení 9 - 17. 4.: Algoritmus CYK. Zásobníkové automaty, vztah k BKJ.
  • Cvičení 10 - 24. 4.: Deterministické a bezprefixové BKJ. Turingovy stroje.

    • Hodnocení
    Na zápočet je třeba alespoň 80 bodů. V zápočtové písemce na konci semestru je možné získat max. 120 bodů, za domácí úkoly max. 9x 2 body, a další 2 body lze získat za aktivitu na cvičeních. Domácí úkoly se budou odevzdávat na papíře na cvičeních (preferováno) anebo v případě nutnosti mailem.