Topic outline

  • General

    • Test 14.9. Quiz
      Restricted Not available unless: Your Email address is akellich@seznam.cz
  • Cvičení J. Bulín

    Restricted Not available unless any of:
    • You belong to cvičení čt 9:00 - Bulín
    • You belong to cvičení st 9:00 - Bulín
  • Cvičení P. Gregor

    • DU1 ze středy 3.3. Assignment
      Restricted Not available unless: You belong to cvičení st 15:40 - Gregor
    • DU1 z pátku 5.3. Assignment
      Restricted Not available unless: You belong to cvičení pá 9:00 - Gregor
    • DU2 ze středy 10.3. Assignment
      Restricted Not available unless: You belong to cvičení st 15:40 - Gregor
    • DU2 z pátku 12.3. Assignment
      Restricted Not available unless: You belong to cvičení pá 9:00 - Gregor
    • DU3 ze středy 17.3. Assignment
      Restricted Not available unless: You belong to cvičení st 15:40 - Gregor
    • DU3 z pátku 19.3. Assignment
      Restricted Not available unless: You belong to cvičení pá 9:00 - Gregor
    • DU4 ze středy 24.3. Assignment
      Restricted Not available unless: You belong to cvičení st 15:40 - Gregor
    • DU4 z pátku 26.3. Assignment
      Restricted Not available unless: You belong to cvičení pá 9:00 - Gregor
    • DU5 ze středy 31.3. Assignment
      Restricted Not available unless: You belong to cvičení st 15:40 - Gregor
    • DU6 ze středy 7.4. Assignment
      Restricted Not available unless: You belong to cvičení st 15:40 - Gregor
    • DU5 z pátku 9.4. Assignment
      Restricted Not available unless: You belong to cvičení pá 9:00 - Gregor
    • DU7 ze středy 14.4. Assignment
      Restricted Not available unless: You belong to cvičení st 15:40 - Gregor
    • DU6 z pátku 16.4. Assignment
      Restricted Not available unless: You belong to cvičení pá 9:00 - Gregor
    • DU8 ze středy 21.4. Assignment
      Restricted Not available unless: You belong to cvičení st 15:40 - Gregor
    • DU7 z pátku 23.4. Assignment
      Restricted Not available unless: You belong to cvičení pá 9:00 - Gregor
    • DU9 ze středy 28.4. Assignment
      Restricted Not available unless: You belong to cvičení st 15:40 - Gregor
    • DU8 z pátku 30.4. Assignment
      Restricted Not available unless: You belong to cvičení pá 9:00 - Gregor
    • DU10 ze středy 5.5. Assignment
      Restricted Not available unless: You belong to cvičení st 15:40 - Gregor
    • DU9 z pátku 7.5. Assignment
      Restricted Not available unless: You belong to cvičení pá 9:00 - Gregor
    • DU10 z pátku 14.5. Assignment
      Restricted Not available unless: You belong to cvičení pá 9:00 - Gregor
    • DU11 ze středy 19.5. Assignment
      Restricted Not available unless: You belong to cvičení st 15:40 - Gregor
    • DU11 z pátku 21.5. Assignment
      Restricted Not available unless: You belong to cvičení pá 9:00 - Gregor
    • DU12 ze středy 26.5. Assignment
      Restricted Not available unless: You belong to cvičení st 15:40 - Gregor
    • DU12 z pátku 28.5. Assignment
      Restricted Not available unless: You belong to cvičení pá 9:00 - Gregor
    • písemka ve středu 2.6. Assignment
      Restricted Not available unless: You belong to cvičení st 15:40 - Gregor
    • písemka v pátek 4.6. Assignment
      Restricted Not available unless: You belong to cvičení pá 9:00 - Gregor
  • Cvičení D. Kuboň

    • Domácí úkol 2 Assignment
      Restricted Not available unless: You belong to cvičení st 14:00 - Kuboň
    • Domácí úkol 3 Assignment
      Restricted Not available unless: You belong to cvičení st 14:00 - Kuboň
    • Domácí úkol 4 Assignment
      Restricted Not available unless: You belong to cvičení st 14:00 - Kuboň
    • Domácí úkol 5 Assignment
      Restricted Not available unless: You belong to cvičení st 14:00 - Kuboň
    • Domácí úkol 6 Assignment
      Restricted Not available unless: You belong to cvičení st 14:00 - Kuboň
    • Domácí úkol 7 Assignment
      Restricted Not available unless: You belong to cvičení st 14:00 - Kuboň
    • Domácí úkol 8 Assignment
      Restricted Not available unless: You belong to cvičení st 14:00 - Kuboň
    • Domácí úkol 9 Assignment
      Restricted Not available unless: You belong to cvičení st 14:00 - Kuboň
    • Domácí úkol 10 Assignment
      Restricted Not available unless: You belong to cvičení st 14:00 - Kuboň
    • Domáci úkol 11 Assignment
      Restricted Not available unless: You belong to 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