Osnova témat

  • Úvod

    • Základní prostor pro diskusi.

  • Obecné

  • Cvičení J. Bulín

  • Cvičení T. Čelko

    Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k cvičení T. Čelko
  • Cvičení V. Majerech

  • Cvičení M. Vomlelová

    Přístup je omezen následujícím způsobem - není dostupné, pokud není vše splněno: Patříte k 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ů

    • Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      Jsem u přijímaček, na testy (12. úlohu apod.) se podívám pozdější odpoledne.

    • Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', po odevzdání píše 0 bodů všem, do večera opravím.

    • Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', do večera opravím.

    • Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', do večera opravím.

    • Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', po odevzdání píše 0 bodů všem, do večera opravím.

    • Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', po odevzdání píše 0 bodů všem, do večera opravím.

    • Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', do večera opravím.

    • Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', po odevzdání píše 0 bodů všem, do večera opravím.

    • Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', po odevzdání píše 0 bodů všem, do večera opravím.

    • Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', do večera opravím.

    • Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', po odevzdání píše 0 bodů všem, do večera opravím.

    • Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      V prvních čtyřech otázkách při chybě jen u deterministických zásobníkových automatů uznávám 0.5 bodu za správně zodpovězený zbytek. Úlohu 12 opravím do večera.

    • Čas: 1 hodina, při 7 a více bodů přijďte na ústní zkoušku.

      12. úlohu opravuji 'ručně', do večera opravím.

  • Cvičení P. Gregor

    • ikona Úkol
      DU1 ze 16.2. Úkol
      Přístup je omezen následujícím způsobem - není dostupné, pokud není splněna aspoň jedna z podmínek:
      • Patříte k cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Patříte k cvičení čt 15:40 - LS 2022/23 (Gregor)
    • ikona Úkol
      DU2a z 23.2. Úkol
      Přístup je omezen následujícím způsobem - není dostupné, pokud není splněna aspoň jedna z podmínek:
      • Patříte k cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Patříte k cvičení čt 15:40 - LS 2022/23 (Gregor)
    • ikona Úkol
      DU2b z 23.2. Úkol
      Přístup je omezen následujícím způsobem - není dostupné, pokud není splněna aspoň jedna z podmínek:
      • Patříte k cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Patříte k cvičení čt 15:40 - LS 2022/23 (Gregor)
    • ikona Úkol
      DU3 z 9.3. Úkol
      Přístup je omezen následujícím způsobem - není dostupné, pokud není splněna aspoň jedna z podmínek:
      • Patříte k cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Patříte k cvičení čt 15:40 - LS 2022/23 (Gregor)
    • ikona Úkol
      DU4 z 16.3. Úkol
      Přístup je omezen následujícím způsobem - není dostupné, pokud není splněna aspoň jedna z podmínek:
      • Patříte k cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Patříte k cvičení čt 15:40 - LS 2022/23 (Gregor)
    • ikona Poznámky
      oznámení Poznámky
      Přístup je omezen následujícím způsobem - není dostupné, pokud není splněna aspoň jedna z podmínek:
      • Patříte k cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Patříte k cvičení čt 15:40 - LS 2022/23 (Gregor)
    • ikona Úkol
      DU5 z 30.3. Úkol
      Přístup je omezen následujícím způsobem - není dostupné, pokud není splněna aspoň jedna z podmínek:
      • Patříte k cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Patříte k cvičení čt 15:40 - LS 2022/23 (Gregor)
    • ikona Úkol
      DU6 z 6.4. Úkol
      Přístup je omezen následujícím způsobem - není dostupné, pokud není splněna aspoň jedna z podmínek:
      • Patříte k cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Patříte k cvičení čt 15:40 - LS 2022/23 (Gregor)
    • ikona Úkol
      DU7a ze 13.4. Úkol
      Přístup je omezen následujícím způsobem - není dostupné, pokud není splněna aspoň jedna z podmínek:
      • Patříte k cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Patříte k cvičení čt 15:40 - LS 2022/23 (Gregor)
    • ikona Úkol
      DU7b ze 13.4. Úkol
      Přístup je omezen následujícím způsobem - není dostupné, pokud není splněna aspoň jedna z podmínek:
      • Patříte k cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Patříte k cvičení čt 15:40 - LS 2022/23 (Gregor)
    • ikona Úkol
      DU8 z 27.4. Úkol
      Přístup je omezen následujícím způsobem - není dostupné, pokud není splněna aspoň jedna z podmínek:
      • Patříte k cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Patříte k cvičení čt 15:40 - LS 2022/23 (Gregor)
    • ikona Poznámky
      oznámení Poznámky
      Přístup je omezen následujícím způsobem - není dostupné, pokud není splněna aspoň jedna z podmínek:
      • Patříte k cvičení čt 14:00 - LS 2022/23 (Gregor)
      • Patříte k cvičení čt 15:40 - LS 2022/23 (Gregor)