Vladan Majerech - NTIN071 Automaty a gramatiky

Last Modified: 18.5.2022

Valid HTML 4.01 Strict

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í 13, cvičení 14

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

Na cvičení jsme velice rychle proletěli o čem budeme hovořit celý rok. Co se týče synchronizace cvičení, rozešel jsem se v následujícím: Na prvním cvičení jsem se zmínil argument mohutnosti množiny jazyků a gramatik, tedy to, že existují i jazyky nepatřící do $\cal L_0$. Taky jsme řešili odstranění nedeterminismu u konečných automatů. Na druhém cvičení jsem zmínil argumenty vedoucí k důkazu pumping lemmat pro bezkontextové i regulární jazyky. Na prvním cvičení jsem standardní okliku pro umožnění prázdného slova v monotónních gramatikách neřekl celou. Koukám, že jsem definoval Turingovy stroje, ale ne, jak při ukončení výpočtu je definován výsledek výpočtu. Definice typicky ignorují pásku a řídí se jen stavem stroje na konci výpočtu. A nás zajímá, jestli nějaký výpočet končí v „koncovém“ stavu.

Cvičení 2

Seznamovali jsme se s konečnými automaty. Nejprve jsme udělali automat pro konečný počet slov. Mírně jsme se zabývali „komentováním programu“. Následně jsme redukovali deterministický automat postupným zjemňováním tříd ekvivalence $\sim_0$, $\sim_1$, $\dots$, $\sim_k=\sim_{k+1}=\sim_\infty=\sim$, kde index značil jak nejvýš dlouhými suffixy jsou dané stavy rozlišitelné. Snažil jsem se ukázat, jak daný formální postup optimalizovat $\dots$ jak si zjednodušit problémy s pojmenováváním tříd ekvivalence, jak dělat „diferenční“ zápis tabulky, že je dobré ušetřit práci a nedělat výpočty týkající se zjemňování jednoprvkových tříd ekvivalence. Stejný postup, bez zápisu se snadnou zpětnou kontrolou jsme si předvedli graficky na grafu daného automatu. Zdůrazňoval jsem, že zjemňování tříd ekvivalence je mnohem efektivnější než udržování úplného grafu informací o rozlišitelnosti stavů.

Redukci automatu jsme následně použili na jednoduchém nekonečném automatu (trie přijímaných slov nebylo konečné) a redukovaný automat vyšel konečný. Výsledný rozklad $\sim_\infty$ byla pravá kongruence s konečným počtem tříd ekvivalence. Což tak trochu z Nerodovy věty dělá prázdné tvrzení $\dots$ pokud redukovaný automat daného jazyka má konečný počet stavů, tak je jazyk rozpoznávaný automatem s konečným počtem stavů. Taky jsme si ukázali redukovaný nekonečný automat pro $0^n1^n$ (zkontrolovali jsme (měli jsme), že je redukovaný), takže pro $0^n1^n$ konečný automat neexistuje.

Pak jsme dokázali, že deterministický 4 stavový automat přijímající $a^5$ přijímá i $a^{5+12}$ (odvodili jsme co máme dokazovat). Následně jsme u dvou třístavových automatů slovně popisovali přijímaný jazyk. U prvního z nich jsme doplnili komentáře/invarianty a zkontrolovali korektnost našeho tvrzení. U druhého jsme komentáře/invarianty nedoplňovali, necháme si to na později (na Kleeneho větu).

Na druhém cvičení jsme si ještě stihli nakreslit automat pro game v Tenisu (a podařilo se mi při tom zmínit Moore a Mealy stroje) a schéma automatu pro set v tenisu bez tiebreaku. Na příští hodině se budeme věnovat jazykovým operacím a tomu, zda jsme schopni z konečných automatů pro jednotlivé jazyky vytvořit konečný automat pro jazyk vzniklý danou jazykovou operací (takže jsou jazyky konečných automatů uzavřené na danou jazykovou operaci).

Cvičení 3

Věnovali jsme se jazykovým konstrukcím a tím jak z konečných automatů přijímajících původní jazyky nakombinovat konečný automat pro výsledný jazyk. Začali jsme množinovýma operacema (průnik, sjednocení, rozdíly, doplněk), pokračovali jsme zřetězením, iteracemi a obracením, udělali jsme vložení/odstranění písmenka, věnovali jsme se levým a pravým kvocientům. Pak jsme zjistili, že jazyky konečných automatů nejsou uzavřené na permutátor. Skončili jsme substitucí a homomorfismem. Kvůli konstrukcím se nám hodilo pracovat s $\lambda$ automaty, takže jsme si zdůvodnili, jak je převést na nedeterministické automaty.

Na první verzi cvičení jsme kvůli substituci řešili tenisový automat. Nezdůraznil jsem, že u substituce potřebujeme, aby jazyky na něž se zobrazují jednotlivá písmenka byly rozpoznávány konečnými automaty. Ve výsledku jsme ověřili, že model, kde na hranách grafu jsou libovolná slova je výpočetně ekvivalentní konečným automatům.

Na druhé verzi cvičení jsme stihli probrat i inverzní homomorfismus a podtrhávací pumping lemma a zadat s ním spojený dlouhodobý domácí úkol.

Když jsme se zbavovali $\lambda$, nevěnovali jsme se případu, kdy na sebe navazuje více $\lambda$ (či dokonce máme cyklus $\lambda$). Možným řešením je nejprve „obarvit„ $\lambda$, pro něž jsme udělali náhradní šipky. $\lambda$ mohou vznikat, ale pro každou dvojici vrcholů $\lambda$ obarvíme nejvýš jednou (nepřidáváme hrany, které již existují), tedy celé obarvování bude trvat konečný počet kroků (množina vrcholů se nemění). Ve chvíli, kdy neexistuje neobarvená $\lambda$, můžeme všechy obarvené odstranit a skončit (alternativou je postupovat podle topologického uspořádání silně souvislých komponent grafu tvořeného hranami s $\lambda$).

Kartézský součin nemusíme dělat z deterministických automatů, ale pro negaci jazyka je nedeterministický automat nepoužitelný (takže při rozdílu kde potřebujeme negovat $\dots$).

Cvičení 4

Na první verzi cviření jsme dělali pumping lemma (včetně podtrhávacího lemma a zadání dlouhodobého domácího úkolu). Následně jsme si připomněli substituci a homomorfismus. Zakončili jsme to mikroprogramováním inverzního homomorfismu.

Na obou verzích cvičení jsme ještě chvíli pracovali s nestandardními jazykovými konstrukcemi.

Pak jsme si povídali o regulárních výrazech a jim odpovídajících jazycích. Zkonstatovali jsme, že naše jazykové konstrukce (ty nejzákladnější) dokáží zkonstruovat konečný automat pro každý regulární výraz.

Na závěr jsme si připomněli Floyd-Warshal algoritmus na hledání všech sledů. Tedy to, že jazyk každého konečného automatu odpovídá regulárnímu výrazu.

Na druhé verzi cvičení jsme měli dost času, abychom pro oblíbený konečný automat zjistili FW algoritmem regulární výraz popisující jeho jazyk. Měli jsme dokonce dost času na to, abychom postup zopakovali v optimalizované variantě a výsledný výraz nejen, že jsme spočítali mnohem rychleji, ale vyšel i výrazně jednodušší. (To že stejnému jazyku odpovídá více regulárních výrazů až tak překvapivé není. Naštěstí tomu vždy odpovídá jediný normalizovaný konečný automat.)

Cvičení 5

Na první verzi cvičení jsme dodělávali konstrukci regulárního výrazu na základě vybraného automatu a získali jsme zkušenost s optimalizací Floyd Warshalova algoritmu pro tyto účely.

Na obou cvičeních jsme se krátce věnovali Moore a Mealy strojům a déle věnovali dvoucestným automatům. Prošli jsme si důkaz s přechodovými posloupnostmi. Pak jsem zadal dlouhodobý domácí úkol týkající se dvoucestných automatů s kamínkem. To byla motivace k důkazu s prefixovými funkcemi. Nakonec jsme se věnovali důkazu se sufixovými funkcemi, ale stihli jsme jej dokončit jen na druhé verzi cvičení.

Na druhé verzi cvičení jsme ještě stihli důkaz ekvivalence tříd jazyků generovaných $L_3$ gramatikami a jazyků rozpoznávaných konečnými automaty.

Cvičení 6

Na obou verzích cvičení jsme se věnovali gramatikám, speciálně bezkontextovým, odvodili jsme si Chomskiho normální formu, pumping lemma, podtrhávací pumping lemma a aplikovali jsme podtrhávací lemma na dokázání nenáležení nějakého konkrétního jazyka do $\cal L_2$.

Na obou cvičeních jsem špatně odhadl nutnou délku slova ve vztahu k počtu neterminálů Chomskiho normální formy ($n$ mělo být ve výrazu o 1 menší ... 1 netrminál stačí délka $2^0+1$ ... chtěli jsme hloubku $n+1$ vrcholů, tedy $n$ hran).

Neuvědomil jsem si, že na pvrní verzi cvičení jsme ještě nedokázali ekvivalenci $\cal L_3$ gramatik a konečných automatů. Tím bychom měli příště začít. Taky mám pocit, že na první verzi cvičení jsem nezmínil, že pro gramatiky generující prázdné slovo máme problém s Chomskiho normální formou (ta jej generovat neumí) je to možno vyřešit tím, že gramatika je pětice, kde pátá složka je booleovská hodnota, která pokud je pravdivá, tak $\lambda$ patří do jazyka gramatiky i pokud jej gramatika negeneruje. (Méně se mi líbí komplikovaná oklika pomocí výjimky v Chomskiho formě umožňující $S\to\lambda$ za podmínky, že $S$ není nikde na pravé straně.)

Na první verzi cvičení jsme si povídali i o tom, co jsou zásobníkové automaty. O vzájemných vztazích různých jejich verzí a o vztahu k $\cal L_2$ jsme si nic odvodit nestihli.

Cvičení 7

Na první verzi cvičení jsme doplnili důkaz ekvivalence jayzků $\cal L_3$ gramatik a konečných automatů.

Na obou verzích cvičení jsme zkoumali nedeterministické i deterministické zásobníkové automaty přijímající koncovým stavem či prázdným zásobníkem. Rozmysleli jsme si možnosti vzájemných simulací. Pak jsme ukázali, že nederetministický automat s jediným stavem (přijímající prázdným zásobníkem) dokáže simulovat všechny zásobníkové autoamaty (na první verzi cvičení 9ne rozdíl od druhé) jsme se moc nezabývali nastartováním simulujícího automatu). Pak už byl jen krůček k tomu, ukázat, ekvivalenci jazyků $\cal L_2$ gramatik a nedeterministických zásobníkových automatů.

Na konci hodiny jsme si ještě hráli s jazyky „na hranici“ $\cal L_2$ a rozhodovali jsme, zda do $\cal L_2$ patří.

Cvičení 8

Programovali jsme v $\cal L_2$ (tvorba monotónních gramatik pro dva jazyky), následně jsme ukazovali, jak převést libovolnou monotónní gramatiku na kontextový normální tvar (a nezpůsobit, že nová gramatika bude generovat něco navíc).

Cvičení 9

Řešili jsme jak vztah $\cal L_1$ a $\cal L_0$ gramatik a nedeterministických (lineárně omezených či neomezených) Turingových strojů, tak (ne)uzavřenost tříd $\cal L_i$ na základní jazykové operace.

Cvičení 10

Počítali jsme příklady z historických písemek.

Cvičení 11

Zabrousili jsme do vyčíslitelnosti a složitosti. Ukázali jsme, že existují jazyky nepatřící do $\cal L_0$ (ne)spočetnost, diagonalizace (Goedelovo číslování strojů). Pak jsme hledali jazyk patřící do $\cal L_0\setminus L_1$. Použili jsme k tomu jazyk patřící do $\hbox{Space}(n^2)\setminus\hbox{Space}(n)$. K jeho konstrukci jsme potřebovali dokázat větu o hierarchii (definovat pojmy $\hbox{Space}(f(n))$, prostorovou konstruovatelnost, ukázali jsme si prostorově nenáročné skládání prostorově nenáročných transformací, naznačili jsme existenci univerzálního stroje a jeho $c_y$ konstantní prostorové zvětšení náročnosti při simulaci stroje $y$). Bavili jsme se o tom, jak by mohla vypadat funkce, která není prostorově konstruovatelná, zmínil jsem Borodinovu větu o mezerách a na druhém cvičeni i její důkaz.

Pak jsme se konečně vrátili k původnímu plánu hodiny a ukázali si univerzálnost Postova korespondenčního problému (nejprve ve variantě s inicializací, pak jsme vymysleli, jak se obejít bez speciálního pravidla pro inicializaci).

Na následujících dvou cvičeních budou zápočtové písemky. Pokud by se někdo nemohl účastnit osobně, pošlete mi (radši den předem e-mail), dostanete zadání e-mailem na začátku hodiny a budete mít čas do konce hodiny odevzdat e-mailem řešení. Můžete si případně o zadání říct přes zoom, pak ale možná chvilku potrvá, než e-mail dostanete.

Cvičení 12

Psali jsme zápočtovou písemku.

Cvičení 13

Psali jsme zápočtovou písemku.

Cvičení 14

Na posledním cvičení jsem prozradil řešení domácího úkolu, který se vyskytl v písemce, načež jsem odpovídal poslední dotazy k automatům a gramatikám a zbytek hodiny jsme volně věnovali hádance nesouvisející s automaty a gramatikami.

Co se týče nešťastníků, kteří nedostali zápočet za písemky, je zde ještě pracná možnost ve formě domácích úkolů. Na požádání e-mailem dostanete přidělen výsledkům písemky odpovídající počet malých přirozených čísel. Každé přirozené číslo kóduje dva příklady. Pokusíte se čísel, které vám byly dány na starost zbavit, což je možno odevzdáním správně vyřešených obou příkladů. Po úspěšné kontrole vám číslo odeberu a pokud vám žádné nezbyde, dostaete zápočet. Pokud ale při kontrole narazím na chybu, oznámím, jaký je protipříklad k neúspěšně vyřešenému příkladu, co vše jsem úspěšně do té doby zkontroloval (můžete se tak některých čísel zbavit a jiných třeba napůl) a přidělím vám číslo navíc. Další příklady nebudu kontrolovat, dokud nedostanu další e-mail.

Příklady pro číslo $x$:
1) Dodejte redukovaný konečný automat přijímající jazyk nad abecedou $\{0,1\}$ slov, odpovídající nejkratším zápisům celých kladných čísel dávajících mod 18 zbytek stejný jako $x$.
2) $L_k$ je jazyk slov nad abecedou $\{0,1\}$ obsahujících posledních 5 cifer binárního zápisu $32+k$ jako podslovo. Dodejte redukovaný automat přijímající jazyk $L_x \setminus L_{x+7}$.