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

  • Общее

    • Test 14.9. Тест
      Ограничено Недоступно, пока не выполнено: Ваше поле Адрес электронной почты имеет значение akellich@seznam.cz
  • Obecné

  • Cvičení J. Bulín

    Ограничено Недоступно, пока не выполнено одно из:
    • Вы принадлежите к группе cvičení čt 9:00 - Bulín
    • Вы принадлежите к группе cvičení st 9:00 - Bulín
  • Cvičení P. Gregor

    • DU1 ze středy 3.3. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 15:40 - Gregor
    • DU1 z pátku 5.3. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení pá 9:00 - Gregor
    • DU2 ze středy 10.3. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 15:40 - Gregor
    • DU2 z pátku 12.3. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení pá 9:00 - Gregor
    • DU3 ze středy 17.3. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 15:40 - Gregor
    • DU3 z pátku 19.3. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení pá 9:00 - Gregor
    • DU4 ze středy 24.3. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 15:40 - Gregor
    • DU4 z pátku 26.3. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení pá 9:00 - Gregor
    • DU5 ze středy 31.3. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 15:40 - Gregor
    • DU6 ze středy 7.4. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 15:40 - Gregor
    • DU5 z pátku 9.4. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení pá 9:00 - Gregor
    • DU7 ze středy 14.4. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 15:40 - Gregor
    • DU6 z pátku 16.4. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení pá 9:00 - Gregor
    • DU8 ze středy 21.4. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 15:40 - Gregor
    • DU7 z pátku 23.4. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení pá 9:00 - Gregor
    • DU9 ze středy 28.4. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 15:40 - Gregor
    • DU8 z pátku 30.4. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení pá 9:00 - Gregor
    • DU10 ze středy 5.5. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 15:40 - Gregor
    • DU9 z pátku 7.5. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení pá 9:00 - Gregor
    • DU10 z pátku 14.5. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení pá 9:00 - Gregor
    • DU11 ze středy 19.5. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 15:40 - Gregor
    • DU11 z pátku 21.5. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení pá 9:00 - Gregor
    • DU12 ze středy 26.5. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 15:40 - Gregor
    • DU12 z pátku 28.5. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení pá 9:00 - Gregor
    • písemka ve středu 2.6. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 15:40 - Gregor
    • písemka v pátek 4.6. Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení pá 9:00 - Gregor
  • Cvičení D. Kuboň

    • Domácí úkol 2 Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 14:00 - Kuboň
    • Domácí úkol 3 Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 14:00 - Kuboň
    • Domácí úkol 4 Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 14:00 - Kuboň
    • Domácí úkol 5 Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 14:00 - Kuboň
    • Domácí úkol 6 Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 14:00 - Kuboň
    • Domácí úkol 7 Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 14:00 - Kuboň
    • Domácí úkol 8 Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 14:00 - Kuboň
    • Domácí úkol 9 Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 14:00 - Kuboň
    • Domácí úkol 10 Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 14:00 - Kuboň
    • Domáci úkol 11 Задание
      Ограничено Недоступно, пока не выполнено: Вы принадлежите к группе cvičení st 14:00 - Kuboň
  • 2.3. Konečné automaty, regulární jazyky, Iterační (pumping) lemma

  • Redukce a ekvivalence automatů

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

  • Deterministické a bezprefixové PDA

  • 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

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

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