Vladan Majerech - NTIN071 Automaty a gramatiky
Last Modified: 19.5.2023
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, poslední cvičení,
Cvičení by měla současně probíhat přes zoom, uvidíme, jak bude fungovat technika. Včas byste měli dostat e-mailem odkaz na google doc. V něm budou (GDPR) odkazy na sdílená videa. 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 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
Na prvním cvičení jsme probrali "extended abstract" toho, co budeme dělat celý rok.
Cvičení 2
Nejdříve jsme zkoušeli číst cizí programy (jen třístavové), třetí z nich nám dal docela zabrat. U prvních dvou jsme snadno nalezli popis jazyků odpovídajících přechodu z počátečního do daného stavu.
Pak jsme si udělali užitečný Mooreův/Mealyho stroj na počítání tenisového skóre. Pak nás ten stroj zajímal jen jako automat rozhodující kdo vyhrál game na základě vítězství míčků a přemýšleli jsme nad vzájemnou zastupitelností stavů. Udělali jsme redukci automatu jak tabulkou zjemňování tříd ekvivalence, tak graficky na grafu automatu.
Na konci hodiny jsme se zamysleli nad jazykovou konstrukcí substituce, která v tenise z automatu rozhodujícího o vítězovi setu na základě vítězství gamů (a předchozího automatu) umožnila vytvořit automat rozhodující vítězství setu na základě jednotlivých míčků.
Cvičení 3
Vymýšleli jsme různé jazykové konstrukce a to jak z automatů pro jednotlivé vstupní jazyky vytvořit automat pro jazyk získaný danou jazykovou konstrukcí. Mnohdy se nám hodilo neomezovat se průběžně na jednoznačnost přechodové funkce, stejně tak se nám často hodilo mít na hranách libovolně dlouhá slova (i prázdná), situaci zjednodušovalo mít jediný vstupní a jediný výstupní stav. Naučili jsme se takový nedeterminisický (lambda) automat převádět na deterministický automat (pro negaci jsme potřebovali deterministickou verzi).
Taky jsme krátce zmínili Nerodovu větu a narazili na jazykovou konstrukci nezachovávající vlastnost být přijímán konečným automatem.
Cvičení 4
Dokázali jsme si podtrhávací pumping lemma pro jazyky přijímané konečnými automaty, zadal jsem dlouhodobý domácí úkol nalézt jazyk $L$, takový, že jak pro $L$ tak pro jeho doplněk platí podrhávací pumping lemma a přitom $L$ není přijímaný konečným automatem.
Pak jsme udělali kostrukce pro kvocienty.
Pokračovali jsme zavedením regulárních výrazů a jim odpovídajícícm jazykům. Uvědomili jsme si, že umíme vytvořit konečný automat pro všechny jazyky odpovídající základním regulárním výrazům, a pro všechny použité konstrukce máme návod jak z konečného automatu pro jazyky operandů vyvořit konečný automat pro výsledek. Víme tedy že pro každý jazyk odpovídající regulárnímu výrazu jsme schopni zkonstruovat konečný automat, který jej přijímá.
Na konci hodiny jsme si uvědomili, že pro zadaný konečný automat Floyd-Warshal algoritmus dokáže najít regulární výraz jemuž odpovídající jazyk je jazykem daného automatu.
Cvičení 5
Na prvním cvičení jsme pro daný automat hledali regulární výraz popisující jeho jazyk (což jsme na druhém cvičení stihli minule). Pak jsme se věnovali dvoucestným automatům (a byl zadán domácí úkol o dvoucestném automatu s kamínkem). Taky jsme se krátce věnovali $L_3$ gramatikám, ukázali jsme si že je můžeme pževést na normalizovaný tvar, takový, že efektivnímu zápisu expanze zcela přirozeně odpovídá nedeterministický konečný automat. (Jen je lepší zvolit variantu, kde jsou neterminály na pravém konci pravé strany.) Současně platilo, že libovolnému nedeterministickému automatu zcela přirozeně odpovídá $L_3$ gramatika v daném normalizovaném tvaru. Příště se nejspíš podíváme na nějakou písemku.
Cvičení 6
Zkoušeli jsme, zda bychom dokázali úspěšně absolvovat písemku. Moc dobře to nedopadlo, ukázalo se, že jsou velké problémy s redukcí autoamtů. V mnoha případech docházelo k chybám při determinizaci automatu.
Cvičení 7
Na sedmém (a úterním osmém) cvičení jsme se věnovali bezkontextovým gramatikám, Chomskiho normálnímu tvaru, pumping lemmatu, podtrhávacímu pumping lematu (pro BKJ), důkazu i použití. Kromě toho jsme si rozmysleli, jak nedeterministicky ověřit, zda dané slovo je generované danou bezkontextovou gramatikou (zjistili jsme, že k tomu, co si potřebujeme pamatovat se perfektně hodí zásobník).
Cvičení 1. po Velikonocích
Hráli jsme si si se slovníkem morseovky, ale museli jsme půlku slova psát pozpáku, protože $\alpha=\alpha$ není bezkontextové (ukázali jsme z pumping lemma). Kromě toho jsme ukázali, že nedeterministické zásobníkové automaty přijímající prázdným zásobnkem nepotřebují stavy.
Cvičení 2. po Velikonocích
Nejprve jsme dokončili ekvivalenci mězi jazyky nedeterministických zásobníkových automatů a jazyků bezkontextových gramatik. Pak jsme ukázali, že normálním tvarem nezkracujících gramatik je nezkracující kontextový tvar, a že normálním tvarem obecných gramatik je obecný kontextový tvar. Na pátečním cvičení jsme zvládli ukázat i ekvivalenci mezi jazyky lineárních Turingových strojů a jazyků nezkracujících gramatik.
Poslední cvičení
Po testovací písemce a dvou skutečných písemkách jsme na posledním cvičení řešili ekvivalenci jazyků rozpoznávaných turingovými stroji s jazyky obecných gramatik. Spočetli jsme počty jazyků i gramatik/strojů, a diagonalizačním argumentem jsme ukázali proč není možno vyjmenovat nespočetně velkou množinu. Věnovali jsme se Postově korespondenčnímu problému, resp. jsme si hráli s Turingovými stroji. Řešili jsme problémy děrné pásky, líného resp. extrémně líného hardwareáře.
Vzhledem k tomu, že existují studenti kteří zápočet za písemky nezískali, je zde ještě záchranná možnost s řešením domácích úkolů, podle pravidel, která jsem oznamoval na cvičení. Ti co si o tuto možnost e-mailem zažádají, dostanou přidělen krátký seznam přirozených čísel. Každé číslo kóduje dvě úlohy, po jejichž úspěšném odevzdání považjeme dané číslo za vyřízené. Po vyřízení všech čísel ze seznamu udělím zápočet. Úlohy opravuji v dávkách a při nalezení první chyby přestávám dávku opravovat, oznámím, co zkontolováno bylo (mohu tak některá čísla prohlásit za vyřízená) a k nevyřízeným číslům přidám jedno další.
Parametrizované úkoly: Nechť dostanete číslo $n$. Pro i od 1 do 4 a parametry $z_i$, $m_i$ po řadě $(3,5,2,4)$ a $(7,11,13,15)$, spočtěte $n_i$ jako zbytek po dělení $(n+z_i)$ číslem $m_i$. Tato čísla $n_1$, $n_2$, $n_3$ a $n_4$ uvádějte s číslem $n$ k identifikaci řešeného úkolu. (I špatně spočtené $n_i$ je považované za chybu.)
Úkol A: Dodejte redukovaný automat pro jazyk nad abecedou $\{0,1\}$ slov obsahujících jako podřetězec binární zápis čísla $n_4$, ale nekončících binárním zápisem čísla $1+n_1$.
Úkol B: Dodejte redukovaný automat pro jazyk nad abecedou $\{0,1\}$ slov odpovídajících nejkratším binárním zápisům kladných celých čísel, která dávají zbytek při dělení 12 stejný jako buď $n_2$ nebo $n_3$. („hodinová ručička na jednom z nejvýš dvou vyznačených míst.“)