Vladan Majerech - NTIN071 Automaty a gramatiky
Last Modified: 27.5.2021
Index
zápočtové písemky, odkazy, cvičení 1, cvičení 2, cvičení 3, cvičení 4, cvičení 5, cvičení 6, cvičení 7, cvičení 8, cvičení 9, cvičení 10, cvičení 11, cvičení 12
Cvičení by měla probíhat přes zoom. Včas byste měli dostat e-mailem odkaz na google doc. Pokud by k tomu z jakéhokoli důvodu nedošlo, kontaktujte mne mailem jmeno.prijmeni@mff.cuni.cz. V google doc by měly být odkazy na zoom i virtuální tabuli udržovány.
Zápočet je udělován za zápočtové písemky, které se konají na 3. a 2. hodině od konce semestru. (Snad se podaří tyto termíny neprošvihnout s ohledem na rektorské, děkanské dny a různé další dny volna). Na písemkách jsou zadávány 4 příklady z nichž je často jeden velmi složitý. Pokud student bez chyby vyřeší dva příklady z písemky, má zajištěn zápočet. Nepodceňujte to, procento úspěšných studentů na první písemce bývá malé.
Zápočtové písemky
Příklady zápočtových písemek z daleké minulosti: Podotýkám, že požadované konečné automaty byly tak malé, že dobře nakreslený graf byl přehlednější než tabulka. Ve vzorových řešeních jsou uvedeny jen tabulky (kreslení na papír je mnohem snazší než v editoru). Schválně, jestli objevíte neznámou chybu.
7.5.2003 E3 10:40-12:10 zadání řešení
12.5.2003 M4 12:20-13:50 zadání řešení (O opravitelné chybě v redukci 1) víme.)
12.5.2003 M4 14:00-15:30 zadání řešení
19.5.2003 M4 12:20-13:50 zadání řešení
19.5.2003 M4 14:00-15:30 zadání řešení
21.5.2003 E3 10:40-12:10 zadání řešení
4.5.2004 E3/E4 zadání řešení
18.5.2005 E1/E2 zadání řešení
Odkazy na obdobné stránky
moje loňské cvičeníCvičení 1
Úvodní cvičení bylo ze zhruba 3/4 ve formě přednášky o tom, co nás v semestru čeká. Ve zbytku hodiny jsme se věnovali zkoumání dvou konečných automatů a programování jednoho konečného automatu. Jeden ze zkoumaných automatů jsme zatím nedoprozkoumali. Obrázky sdílené tabule, na níž cvičení proběhlo jsou ve sdíleném dokumentu, pokusíme se je v dokumentu udržet (budeme psát před ně). Nahrávka hodiny trpí tím, že většinu času nenahrává sdílenou tabuli, takže z ní má smysl spíš jen zvuková stopa. Nejspíš ji nezveřejním ani po skončení semestru.
Cvičení 2
Nejprve jsme řešili případ automatu s malým počtem stavů a vzájemného vztahu přijímání slov dostatečné délky nad jednopísmennou abecedou. Úlohu jsme řešili ve skupinkách.
Následně jsme si povídali o pumping lemma, zobecněném pumping lemma (kde měření jsou v počtu podtržených pozic), což umožňuje například pro $a^+b^nc^n+b^*c^*$ ukázat nepřijímání konečným automatem. Trochu jsem pohanil Nerodovu větu a přeložil jsem její důkaz neexistence konečného automatu pro jazyk $0^n1^n$ na důkaz potřeby nekonečného počtu stavů.
Pak jsme si ještě ve skupinkách hráli s automatem počítajícím skóre v tenisovém gemu.
Ve společné části jsme řešili, jak by vypadal automat počítající tenisový set (bez tiebreaku) za pomocí již zkonstruovaného automatu pro gem. Naznačil jsem, že v blízké budoucnosti takové konstrukci budeme říkat substituce.
Tenisový gem jsme využili i pro zmínku o Moorovým a Mealyho strojích, nicméně redukci jsme prováděli jen s ohledem na přijímaný „dvojjazyk“. Redukci jsme provedli nejprve „odhadem“, vzledem k blížícímu se konci hodiny jsem naznačil, jak si člověk pro sebe redukci může udělat bez “auditní stopy„. Algoritmem pro redukci včetně „auditní stopy“ začneme příště.
Z cvičení byl zadán dobrovolný dlouhodobý domácí úkol nalézt jazyk $L$, který není přijímaný konečným automatem a přitom jak pro $L$ tak pro doplněk $\overline{L}$ jazyka $L$ platí podtrhávací pumping lemma.
Cvičení 3
Na cvičení jsme si udělali slíbenou redukci včetně auditní stopy, následně jsme se věnovali jazykovým kontrukcím. K tomu se nám hodilo zavést si lambda automaty (a obecně nedeterministické automaty). Prošli jsme standardní konstrukce $\cup,\cap,\setminus,\overline{}$, náledně $.,^*,^+$, pak jsme přidali vložení/vypuštění písmene, kvocienty a převracení. Homomorfismy a substituce budeme probírat příště.
Cvičení 4
Na cvičení jsme dokončili homomorfismy, substituce a inversní homomorfismy, následně jsme se věnovali Kleeneho větě a (zobecněnému) Floyd Warshalově algoritmu. Nakonec jsme se věnovali dalším jazykovým konstrukcím, (které měly kvadratický či kubický nárůst stavů před determinizací).
Cvičení 5
Věnovali jsme se především dvoucestným automatům, dorozmysleli jsme si konstrukci nedeterministického automatu založeného na přechodových posloupnostech. Následně jsem ukázal deterministickou konstrukci založenou na prefixové přechodové funkci (konstrukce jsme dělali pro nedeterministické dvoucestné automaty). Zadal jsem dlouhodobý domácí úkol na redukci dvoucestného automatu s jedním kamínkem na deterministický konečný automat (v přechodové funkci je v parametrech i počet kamínků ležících na políčku pod hlavou a počet kamínků v řídící jednotce, u jednokamínkového automatu je součet těchto hodnot nejvýš 1, v přechodové funkci je taky napsáno, zda má kamínek skončit na pásce či v řídící jednotce ... za podmínky, kdy součet byl 1). Příště ještě začneme s nedeterministickou konstrukcí založenou na sufixové přechodové funkci, což by se pro řešení DDU mohlo hodit.
Cvičení 6
Jak jsem slíbil, věnovali jsme se konstrukci dvoucestného automtu založené na sufixové přechodové funkci. V dalších hodiných bychom už měli dělat jednodušší věci.
Cvičení 7
Věnovali jsme se zásobníkovým automatům a jejich vztahu k bezkontextovým gramatikám.
Cvičení 8
Věnovali jsme se bezkontextovým gramatikám. Odvodili jsme Chomskiho normální formu a podtrhávací pumping lemma.
Cvičení 9
Zkusili jsme si cvičně jednu z historických písemek. Procovali jsme v místnostech (legrační bylo, že jsme měli 3 lidi ve stejné fyzické místnosti ale ve 3 virtuálních). První skupina měla až na žumpu správně druhý příklad. Druhá skupina měla správně všechny tři řešené příklady (na žumpu jsem průběžně upozornil). Třetí skupina neměla správně žádný příklad. Čtvrtá skupina měla správně jak první, tak až na žumpu druhý příklad.
Ukazuje se, že se neřídíte tím, co jste jednou zaslechli na cvičení, takže nepracujete systematicky. Proč když dělám kartézský součin tak umísťuji vrcholy do roviny náhodně? Čitelnost programu (i když to je obrázek) přispívá k snadnějšímu ladění, takže snižuje pravděpodobnost chyby.
Redukci automatu jste vesměs dělali algoritmem s velkou asymptotickou časovou složitostí.
Regulární výraz jste hádali, místo použití např. Floyd-Warshal algoritmu, jak jsme dělali na cvičení. Jen druhá skupina to uhodla dobře (důkaz si necháme na cvičení, u ostatních jsem našel protipříklady).
Cvičení 10
Předvedl jsem vzorové řešení písemky a pak jsme se věnovali deterministickým bezkontextovým jazykům a udělali jsme jeden příklad na pumping lemma (bezkontextových jayzků). Příští týden je rektorský den a další dva týdny píšeme písemky.
Cvičení 11
Psali jsme písemku. Dopadla docela dobře, přesto budeme muset příští týden psát opět (ti co získali zápočet mají volno, přijdou až na poslední cvičení).
Cvičení 12
Psali jsme druhou písemku.