Section outline

  • Общее

    Свернуть всё Развернуть всё

  • Cvičení J. Bulín

  • Cvičení J. Mestek

    Informace ke cvičením Jakuba Mesteka -  úterý 9:00 v S7, pátek 10:40 v S7

  • Cvičení V. Majerech

  • Cvičení M. Vomlelová

  • Konečné automaty, regulární jazyky, Iterační (pumping) lemma

    • Students must
      Mark as done

      V 2019 přednášce přeskočte úvod na 3m:41s, čas 1h:11m by se měl vejít do konce dnešní přednášky (koncem v čase 1h:03, tj. po součinovém automatu, přijdete jen o ten bankovní příklad).

      https://is.mff.cuni.cz/prednasky/prednaska/NTIN071/1

      Slajdy z doby přednášky jsou nazvány 'Tabule' a jsou ke stažení pod videem.

      Oprava: 9:07 Turingův stroj má sice oboustrannou pásku, ale to není důležité. Klíčové je, že na tu pásku může psát a pohybovat se po ní v libovolném směru.

    • Konečné automaty, PL pro regulární jazyky Тест
      Students must
      Mark as done
    • Slajdy 1 Файл
      Students must
      Mark as done

      Aktualizováno 18.2.2025.

  • 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

  • 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.

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

    • Na tabuli v 7. přednášce v čase 14:42 je chyba, v instrukci i,Z0 → ZZ0 má být i,Z0 → ZZZ0. Přijímáme první chybu, tedy slovo ie nemáme přijmout, teprve až je o jedno e navíc.

      Nakonci (min 23:18) poslení  e sebere Z  ( e,Z →λ) a pak λ krok do přijímajícího stavu (λ,Z0 → λ).

    • Zásobníkové automaty úvod Тест
      Students must
      Mark as done
    • Students must
      Mark as done

      Ke vztahu bezkontextových gramatik a zásobníkových automatů se ještě vrátíme, nebylo dokončeno.

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

    • Students must
      Mark as done

      9. video přednáška 2019

      Prvních 15 min
      'opakování' pumping lemmatu a jeho použití. Kdo si je jistý, že ho umí, může přeskočit. Kdo ne, je důležité umět či se hlásit cvičícímu nebo mě že mu není jasné.
      0:15-0:35
      CYK - algoritmus náležení slova do jazyka; tato 'snadná' otázka u obecných gramatik a Turingových stromů už snadná nebude.
      0:35-0:43:28
      Deterministické zásobníkové automaty
      0:43:28- 0:54:40
      přeskočte, rozšiřující a zamotala jsem se tam. Pro hloubavé: prostřední varianta je správně: bez lambda transakcí, hranu vedu do sourozence cíle plus y přepíšu na z; Pak výsledek odpovídá slajdu.
      0:54:40-1:06
      Vajíčko: naučte se nazpaměť; pokud možno i s důkazy, že jazyky do tříd patří a do menších nepatří.
      1:06-1:10:43
      (Ne)jednoznačnost gramatik - můžete vynechat
      1:10:43
      Uzávěrové vlastnosti (první půl): Bezkontextové jazyky nejsou uzavřené na průnik, jsou na sjednocení, konkatenaci, průnik s regulárním jazykem.
      Pozn: 1:14:08 chybí pravá složená závorka na tabuli za {S->S1 S2
      na slajdu 190 opraven regulární jazyk F na R.
    • CYK, Uzávěrové vlastnosti, Determinizmus Тест
      Students must
      Mark as done

      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.

    • Students must
      Mark as done

      10. video přednáška 2019

      Uzávěrové vlastnosti reguláních, bezkontextových a deterministických bezkontextových jazyků.

      (58:37: zůstanu s prázdým bufferem, nikoli zásobníkem)

    • Slajdy: Deterministické PDA, uzávěrové vlastnosti Файл

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

    • Kontextové gramatiky, Lineárně omezené automaty Тест
      Students must
      Mark as done
    • Students must
      Mark as done

      11 video-přednáška

      Je docela hutná. Nejdůležitější je znát všechny definice a věty (což není moc) a umět napsat Turingův stroj rozpoznávající daný jazyk.

    • Slajdy k přednášce Файл
    • Slajdy 2025 Файл

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

    • Students must
      Mark as done

       12. video přednáška

      Kontextové a monotónní gramatiky a lineárně omezené automaty, diagonální a univerzální jazyk

      Důležité znát: definice, věty, umět napsat kontextovou/monotónní gramatiku k uvedeným a velmi podobným jazykům, případně popsat Turingův stroj dané jazyky přijímající (většinou mi stačí vámi vybraná metoda, zvlášť když znáte větu přijímá lin. omez. aut. právě když existuje kontextová gramatika.

      Diagonální a univerzální jazyk.

      Je toho hodně, jak jsem ostatně měla dojem v 1:08:17.  

      Opravy k řeči, slajdy jsou pokud vím dobře:

      8:45  a^nb^nC^n není bezkontextový, je kontextový.
      33:27 generuji monotónní gramatiku, kterou z předchozího umím přepsat na kontextovou.

      48:29 jsou rekruzivní, nejsou KONTEXTOVÉ, JSOU rekurzivně spočetné. Obrázek správně.
      58:43 přijímá nulu, ne prázný řetězec (to by musel přijmout po přečtení blank, 000)

      1:04-1:08:17 lze přeskočit, nevěřte mi že 1:08:17 přednáška končí ;-))

  • Problém zastavení, PCP, (Ne)rozhodnutelné problémy o CFG

    • Students must
      Mark as done

      13. video přednáška Nerozhodnutelné problémy


      Důkazy propojují myšlenky dohromady, doporučuji shlédnout celé. To co bych ráda, abyste z přednášky znali, je v náledujcících minutách:
      0-7:00
      Nerozhodnutelné problémy, redukce problému
      12:45-22:46
      Problém zastavení (Halting problém), Postův korespondenční problém (PCP)
      1:01:14-1:25:17
      Věta: PCP je nerozhodnutelný. (důkaz před tím přeskočen)
      Rozhodnutelné a nerozhodnutelné problémy pro bezkontextové gramatiky.

    • Slajdy Nerozhodnutelné problémy Файл

  • Časová složitost

  • Prostorová složitost

  • Archiv testů

  • Cvičení P. Gregor

    • link na cvičení P. Gregora (procvičované příklady) Гиперссылка
      Students must
      Mark as done
    • Students must
      Mark as done

      V LS 2022/23 cvičení probíhají ve čtvrtek od 14:00 (S10) a 15:40 (S6). Pro odevzdávání DU přes Moodle se přihlaste do příslušné skupiny.

    • DU1 ze 16.2. Задание
    • DU2a z 23.2. Задание
    • DU2b z 23.2. Задание
    • DU3 z 9.3. Задание
    • DU4 z 16.3. Задание
    • oznámení Рабочая тетрадь
    • DU5 z 30.3. Задание
    • DU6 z 6.4. Задание
    • DU7a ze 13.4. Задание
    • DU7b ze 13.4. Задание
    • DU8 z 27.4. Задание
    • oznámení Рабочая тетрадь