Aperçu des sections

  • Généralités

    • Test 14.9.
      Accès restreint Non disponible à moins que : Votre Adresse de courriel soit exactement akellich@seznam.cz
  • Cvičení J. Bulín

    Accès restreint Non disponible à moins que l'une des conditions suivantes soit remplie :
    • Vous soyez membre de cvičení čt 9:00 - Bulín
    • Vous soyez membre de cvičení st 9:00 - Bulín
  • Cvičení P. Gregor

    • DU1 ze středy 3.3. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 15:40 - Gregor
    • DU1 z pátku 5.3. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení pá 9:00 - Gregor
    • DU2 ze středy 10.3. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 15:40 - Gregor
    • DU2 z pátku 12.3. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení pá 9:00 - Gregor
    • DU3 ze středy 17.3. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 15:40 - Gregor
    • DU3 z pátku 19.3. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení pá 9:00 - Gregor
    • DU4 ze středy 24.3. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 15:40 - Gregor
    • DU4 z pátku 26.3. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení pá 9:00 - Gregor
    • DU5 ze středy 31.3. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 15:40 - Gregor
    • DU6 ze středy 7.4. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 15:40 - Gregor
    • DU5 z pátku 9.4. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení pá 9:00 - Gregor
    • DU7 ze středy 14.4. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 15:40 - Gregor
    • DU6 z pátku 16.4. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení pá 9:00 - Gregor
    • DU8 ze středy 21.4. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 15:40 - Gregor
    • DU7 z pátku 23.4. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení pá 9:00 - Gregor
    • DU9 ze středy 28.4. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 15:40 - Gregor
    • DU8 z pátku 30.4. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení pá 9:00 - Gregor
    • DU10 ze středy 5.5. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 15:40 - Gregor
    • DU9 z pátku 7.5. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení pá 9:00 - Gregor
    • DU10 z pátku 14.5. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení pá 9:00 - Gregor
    • DU11 ze středy 19.5. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 15:40 - Gregor
    • DU11 z pátku 21.5. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení pá 9:00 - Gregor
    • DU12 ze středy 26.5. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 15:40 - Gregor
    • DU12 z pátku 28.5. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení pá 9:00 - Gregor
    • písemka ve středu 2.6. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 15:40 - Gregor
    • písemka v pátek 4.6. Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení pá 9:00 - Gregor
  • Cvičení D. Kuboň

    • Domácí úkol 2 Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 14:00 - Kuboň
    • Domácí úkol 3 Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 14:00 - Kuboň
    • Domácí úkol 4 Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 14:00 - Kuboň
    • Domácí úkol 5 Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 14:00 - Kuboň
    • Domácí úkol 6 Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 14:00 - Kuboň
    • Domácí úkol 7 Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 14:00 - Kuboň
    • Domácí úkol 8 Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 14:00 - Kuboň
    • Domácí úkol 9 Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 14:00 - Kuboň
    • Domácí úkol 10 Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de cvičení st 14:00 - Kuboň
    • Domáci úkol 11 Devoir
      Accès restreint Non disponible à moins que : Vous soyez membre de 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