Chomského normální forma, Pumping lemma pro CFG
Osnova sekce
-
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.
-
Studenti musíOznačit jako hotovo
Nula bodů za jednu chybu v zaškrtávání je nepříjemné, technicky neumím změnit počítání. Tady můžete upravovat, ve výsledném testu rozdělím do jednotlivých otázek nebo nějak vyřeším.
-