Automaty a gramatiky - cvičení

Letní semestr 2022/23 (LS 2021/22)

Rozvrh: čtvrtek od 14:00 v S10 a od 15:40 v S6
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 - 16. 2.: Konečné automaty. Pumping lemma.
  • Cvičení 2 - 23. 2.: Myhill-Nerodova věta. Stavová ekvivalence.
  • Cvičení 3 - 09. 3.: Homomorfismus automatů. Automatová kongruence. Redukt. Nedeterministické konečné automaty.
  • Cvičení 4 - 16. 3.: NKA s lambda-přechody. Uzávěrové vlastnosti třídy regulárních jazyků. Řetězcové operace s jazyky.
  • Cvičení 5 - 23. 3.: Kvocienty. Kleeneho věta.
  • Cvičení 6 - 30. 3.: Kvíz. Regulární výrazy.
  • Cvičení 7 - 06. 4.: Dvoucestné automaty. Gramatiky.
  • Cvičení 8 - 13. 4.: Pravé lineární a bezkontextové gramatiky.
  • Cvičení 9 - 27. 4.: Chomského normální tvar. Pumping lemma pro BKJ, CYK algoritmus, zásobníkové automaty.
  • Cvičení 10 - 04. 5.: Zásobníkové automaty, vztah k BKJ. Deterministické a bezprefixové BKJ, uzávěrové vlastnosti.
  • Cvičení 11 - 11. 5.: Kontextové gramatiky. Turingovy stroje. Rekurzivní a rekurzivně spočetné jazyky.

    • Hodnocení
    Bude založené na bodech získaných za domácí úkoly v průběhu semestru a zápočtovou písemku na konci. Další bod za aktivitu na cvičeních. Domácí úkoly se budou odevzdávat fyzicky na cvičeních (preferováno) anebo elektronicky přes Moodle. V tom případě je třeba se přihlásit do skupiny v Moodle k tomuto cvičení.