Тематический план

  • Obecné

  • Cvičení J. Bulín

  • Cvičení T. Čelko

    Недоступно, пока не выполнено: Вы принадлежите к группе cvičení T. Čelko
  • Cvičení V. Majerech

  • Cvičení M. Vomlelová

    Недоступно, пока не выполнено: Вы принадлежите к группе cvičení M. Vomlelová (obě)
  • Konečné automaty, regulární jazyky, Iterační (pumping) lemma

    • Upraveny požadavky ke zkoušce a na konci přidán algoritmus hledání dosažitelných stavů.

  • Redukce a ekvivalence automatů

  • nedeterminismus, λ-NFA, množinové a řetězcové operace nad jazyky

  • Kleenova věta, regulární výrazy, Homomorfismus, inverzní homomorfismus

  • Příklad na homomorfizmy, Dvousměrné automaty, Mooreův a Mealyho stroj

  • Gramatiky, Chomského hierarchie, L3 a FA, lineání gramatiky, CFG

  • Zásobníkové automaty, přijímání stavem, prázdným zásobníkem, vztah s CFG

  • Deterministické a bezprefixové PDA

    • Test možná předbíhá cvičení; teď můžete tipovat, je to ukázka úloh, které vás mohou potkat v závěrečném testu.

  • Chomského normální forma, Pumping lemma pro CFG

    Na konci 8. přednášky je "Pumping (iterační) lemma pro bezkontextové jazyky". Obě pumping lemmata a definice věcí v Chomského hierarchii považuji za nejdůležitější základ toho, co máte umět u zkoušky.

    Pokud si nejste jisti, že stihnete shlédnout toto video do konce, přeskočte na minutu 31., do minuty 31 je převod zásobníkového automatu na gramatiku. 

    Naopak 9. přednáška začíná opakováním Pumping lemmatu a dalšími příklady. Můžete se podívat nebo použít na zopakování po velikonocích.

    Řešení příkladu na konci přednášky není úplné. Rozdělení na vx nemůže obsahovat zároveň 0 a 2. Pokud obsahuje 0 nebo 2, poruší se rovnost počtu 0 a 2, jak je řešeno na přednášce.

    Je třeba ještě zvážit variantu, že vx neobsahuje ani 0 ani 2. Protože je vx neprázdné, obsahuje 1 a pumpováním se poruší rovnost počtu 0 a 1.

  • Uzávěrové vlastnosti CFL, Dyckovy jazyky

  • Uzávěrové vlastnosti bezkontextových jazyků, Dyckovy jazyky

  • Deterministické a nedeterministické Turingovy stroje, Gramatiky Typu 0 (obecné gramatiky)

  • Dělící čára minulosti a budoucnosti

  • Diagonální jazyk, Univerzální TM, algoritmicky nerozhodnutelné problémy, Postův korespondenční problém

  • Časová a prostorová složitost

  • Archiv testů

  • Cvičení P. Gregor

    • Задание icon
      DU1 ze 16.2. Задание
      Недоступно, пока не выполнено одно из:
      • Вы принадлежите к группе cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Вы принадлежите к группе cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Задание icon
      DU2a z 23.2. Задание
      Недоступно, пока не выполнено одно из:
      • Вы принадлежите к группе cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Вы принадлежите к группе cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Задание icon
      DU2b z 23.2. Задание
      Недоступно, пока не выполнено одно из:
      • Вы принадлежите к группе cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Вы принадлежите к группе cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Задание icon
      DU3 z 9.3. Задание
      Недоступно, пока не выполнено одно из:
      • Вы принадлежите к группе cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Вы принадлежите к группе cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Задание icon
      DU4 z 16.3. Задание
      Недоступно, пока не выполнено одно из:
      • Вы принадлежите к группе cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Вы принадлежите к группе cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Рабочая тетрадь icon
      oznámení Рабочая тетрадь
      Недоступно, пока не выполнено одно из:
      • Вы принадлежите к группе cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Вы принадлежите к группе cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Задание icon
      DU5 z 30.3. Задание
      Недоступно, пока не выполнено одно из:
      • Вы принадлежите к группе cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Вы принадлежите к группе cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Задание icon
      DU6 z 6.4. Задание
      Недоступно, пока не выполнено одно из:
      • Вы принадлежите к группе cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Вы принадлежите к группе cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Задание icon
      DU7a ze 13.4. Задание
      Недоступно, пока не выполнено одно из:
      • Вы принадлежите к группе cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Вы принадлежите к группе cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Задание icon
      DU7b ze 13.4. Задание
      Недоступно, пока не выполнено одно из:
      • Вы принадлежите к группе cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Вы принадлежите к группе cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Задание icon
      DU8 z 27.4. Задание
      Недоступно, пока не выполнено одно из:
      • Вы принадлежите к группе cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Вы принадлежите к группе cvičení čt 15:40 - LS 2022/23 (Gregor)
    • Рабочая тетрадь icon
      oznámení Рабочая тетрадь
      Недоступно, пока не выполнено одно из:
      • Вы принадлежите к группе cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Вы принадлежите к группе cvičení čt 15:40 - LS 2022/23 (Gregor)