Vladan Majerech - NTIN071 Automaty a gramatiky
Last Modified: 21.5.2019
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
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 je malé.
Zápočtové písemky
Příklady zápočtových písemek z 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).
7.5.2003 E3 10:40-12:10 zadání řešení
12.5.2003 M4 12:20-13:50 zadání řešení
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 konaném cvičení jsem dělal přehled toho, co je obsahem předmětu Automaty a gramatiky. Připoměli jsme si co jsou písmenka, co slova, co podslova a co jazyky. Popsal jsem jak funguje systém přepisovacích pravidel a jaký generuje jazyk, rozlišil jsem používanou abecedu na terminální a neterminální a průnikem s jazykem všech slov nad terminální abecedou jsme dostali jazyk generovaný gramatikou. Pak jsme definovali množiny jazyků tzv. třídy Chomskiho hierarchie.
$\cal L_0$ odpovídající gramatikám bez omezení, (dá se ukázat, ale neukazovali jsme, že existuje ekvivalentní gramatika (generuje stejný jazyk), která má všechna pravidla tvaru $\alpha X\beta\to\alpha\gamma\beta$, kde $X$ je neterminál a $\alpha$, $\beta$, $\gamma$ slova). $\cal L_0$ odpovídají jazyky rozpoznatelné Turingovými stroji (zastaví se na slovech jazyka) (opačný směr důkazu nebyl ani naznačen).
$\cal L_1$ odpovídají nezkracujícím gramatikám, tedy gramatikám, kde levá strana pravidel nesmí být delší než pravá. Dá se ukázat, ale neukazovali jsme, že existuje ekvivalentní gramatika, kde všechna pravidla jsou tvaru $\alpha X\beta\to\alpha\gamma\beta$, kde $X$ je neterminál a $\alpha$, $\beta$, $\gamma$ slova a navíc délka slova $\gamma$ je aspoň délka slova tvořeného jediným neterminálem $X$. Kvůli tomuto speciálnímu tvaru se $\cal L_1$ také říká kontextové gramatiky, ačkoli kontextovost je vlastnost už $\cal L_0$, takže odlišující je až kontextové nezkracující, a kontextovost není to, co je v tom spojení důležité. Nezkracování je limitující podmínka z hlediska nastartování procesu odvozování, který standardně začíná jedním specifikovaným neterminálem. To neumožňuje standardně vygenerovat prázdné slovo. Řešením je například přidat k definici gramatiky booleovskou informaci, zda má být prázdné slovo přidáno mezi slova generovaná gramatikou. $\cal L_1$ odpovídají jazyky přijímané jednopáskovými Turingovými stroji, které nezapisují na pásku mimo místa popsaná vstupem (opačný směr důkazu nebyl ani naznačen). (V tomto případě se vždy zastaví a oznámí, zda slovo do jazyka patří.) Zjištění, zda slovo je generované kontextovou gramatikou je PSpace úplný problém (bez důkazu).
$\cal L_2$ odpovídají bezkontextovým gramatikám, neboli gramatikám, kde na levé straně je vždy slovo tvořené jediným neterminálem. (dá se ukázat, ale nedokazovali jsme, že existuje ekvivalentní gramatika v Chomskiho tvaru, kde pravá strana je vždy buď jediný terminál, nebo dva neterminály.) Bezkontextovost umožnuje efektivnější popis odvození, kde místo posloupnosti odvozených slov kreslíme strom odvozování. Nezáleží totiž na pořadí odovzování a můžeme vždy použít například levou derivaci. Odvození podle levé derivace není problém zkontrolovat nedeterministickým zásobníkovým strojem. $\cal L_2$ odpovídají jazyky rozpoznávané nedeterministickými zásobníkovými automaty (opačný směr důkazu nebyl ani naznačen).
$\cal L_3$ odpovídají gramatikám, kde každá má zafixovanou stranu (pravá/levá) a levá strana pravidel je tvořena jediným neterminálem (bezkontextovost) a pravá má nejvýš jeden neterminál a ten se smí vyskytovat jedině jako první na zafixované straně slova. Ukázali jsme, že existuje ekvivalentní gramatika tvaru, kde je na pravé straně pravidel kromě případného neterminálu právě jeden terminál. $\cal L_3$ odpovídají jazyky rozpoznávané konečnými automaty (zatím bez důkazu).
Na dotaz, zda platí nějaké inkluze v dané hierarchii zaznělo $\cal L_3\subset\cal L_2\subset\cal L_1\subset\cal L_0$ (bez důkazu).
K tomuto přehledu se budeme v průběhu roku vracet a doplňovat informace a důkazy.
V posledních čtyřech minutách jsme pro dané automaty zjišťovali, jaké přijímají jazyky (nekomentované programy). Jeden byl jednoduchý, druhý A0>A,A1>B,B0>A,B1>C,C0>B,C1>C; kde B je počáteční a koncový stav zůstal na přemýšlení.
Cvičení 2
Dostali jsme se do stavu, kdy na obou cvičeních již byl probrán automat na sehrávku jedné hry v tenisu. Na úterním cvičení jsme si při tom procvičili redukci automatu. Kromě toho jsme si trochu povídali o Nerodově větě.
Na pátečním cvičení jsme se zabývali dokazováním toho, že jazyk není regulární. Konstrukce nekonečného redukovaného automatu (Nerodova věta) nám umožnila ukázat na $k$ stavů (tříd pravé kongruence), které jsou odlišeny sufixy. Konstruovat nekonečný automat většinou není dobrý nápad a tak jsme přešli k pumping lemma. Dokázali jsme ho, vyslovili, ukázali příklad jazyka Lpump, který je možno pumpovat, ale není přijímaný konečným automatem. Pak jsme zkusili pozměnit pumpování lemma pomocí podtržení písmen a ignorovvání nepodtržených písmen v počítání délek slov. S tímto lemma již bylo možno o jazyku Lpump ukázat, že není rozpoznatelný konečným automatem.
Za dlouhodobý domácí úkol bylo dokázat či vyvrátit, zda eistuje jazyk nepřijímaný konečným automatem, pro nějž i jehož doplněk platí podtrhávací pumping lemma.
Taky jsme si hráli s jazykem $a^{n^2}$ a s tím, zda pro čtyřstavový automat přijímající $a^5$ o některém ze slov $a^{16}$, $a^{17}$, $a^{18}$, $a^{19}$ víme, zda jej taky přijímá.
Pak jsme začali probírat jazykové konstrukce a zkoušet je implementovat pomocí stavební bloků odpovídajícm konečným automatům pro jednodušší jazyky. Podařilo se nám implementovat zřetězení, iterace, rozdíl, průnik, symetrický rozdíl, sjednocení, vypuštění jednoho písmene „a“, vložení jednoho písmene „a“. Používali jsme nedeterministické automaty s lambda kroky. Dvakrát měla první navržená konstrukce chybu, protože nebyla použita orientovaná lambda hrana.
Cvičení 3
Na dalším cvičení jsme nejprve řešili vztah konečných automatů a regulárních výrazů a jazyků. Vzhledem ke konstrukcím z předchozího cvičení nebylo problém dokázat, že pro každý regulární výraz jsme schopni zkonstruovat automat přijímající jazyk odpovídající danému regulárnímu výrazu. K dokončení důkazu Kleeneovy věty jsme potřebovali ukázat, že jazyk rozpoznávaný libovolným konečným automatem je možno popsat regulárním výrazem. K tomu jsme použili Floyd-Warshal algoritmus (jen jsme na nacházené sledy neaplikovali „operátor vybírající minimální sled“). Algoritmus jsme si vyzkoušeli na oblíbeném automatu a rozmysleli jsme si, kolik se dalo ušetřit práce, pokud bychom si předem rozmysleli, jaké mezivýsledky budeme ještě potřebovat.
Pak jsme se vrátili k jazykovým konstrukcím. Ukázali jsme si konstrukce pro kvocienty, jazyk slov daného jazyka zapsaných pozpátku, homomorfismus, substituci. Substituci jsme si ukázali na setu v tenisu, kde z jazyka pro set v abecedě vyhraných gemů a z jazyka pro vyhraný gem na základě vyhraných míčků vytvořit jazyk pro celý set na základě vyhraných míčků. Za domácí úkol bylo rozmyslet si, zda konstrukce jazyka vzniklého permutací písmen slov jiného jazyka (daného konečným automatem) je možno realizovat konečným automatem.
Cvičení 4
Na cvičení jsme se nejprve věnovali dvojcestným automatům. Nejprve jsme si z přednášky zopakovali důkaz s přechodovými posloupnostmi. Pak jsme udělali důkaz s prefixovými přechodovými funkcemi. Zakončili jsme to náznakem důkazu se sufixovými přechodovými funkcemi, jejichž nedeterministický design (nedeterministicky predikujeme budoucnost a větve, kde predikce selhala zahazujeme) je náročný na představivost. Zadal jsem dlouhodobý domácí úkol na konečné automaty s jedním kamínkem.
Pak jsme se věnovali dalším jazykovým konstrukcím. Nejprve jsme vyvrátili možnost tvorby permutační konstrukce, pak jsme udělali konstrukci dělající slova $vu$ ze slov $uv$ jazyka a obdobnou konstrukci s otáčením podslov.
Nakonec jsme se věnovali tvorbě konkrétního automatu pro rozdíl jazyků *aba* a *bab*.
Cvičení 5
Cvičili jsme bezkontextové gramatiky. Začali jsme tím, že umíme bezkontextovou gramatikou vygenerovat $0^n1^n$. (Triviální důsledek na ostrost inkluze $\cal L_3\subset L_2$ jsme nezmiňovali). Pak jsme si uvědomili, že jsme každou bezkontextovou gramatiku schopni předělat na nezkracující bezkontextovou gramatiku (prázdné slovo případně přijímá deklarací). Čímž jsme dostali $\cal L_2\subseteq L_1$.
Pak jsme pokračovali dále v transformací gramatiky a ukázali jsme, že existuje ekvivalentní v Chomskiho normální formě. Chomskiho normální formu jsme využili na důkaz obdoby pumping lemmatu pro jazyky rozpozávané konečným automatem. Následně jsme pokračovali k podtrhávací obdobě pumping lemmatu.
Pumping lemma jsme využili k důkazu toho, že $0^n1^n2^n$ není bezkontextový jazyk. Pak jsme si dále hráli s jazyky $0^i1^j2^k$ kde pro $i$, $j$, $k$ jsme postupně stanovovali různé podmínky. Po úvodní $i=j=k$ jsme zkusili $i<j<k$ (a stačilo obyčejné pumping lemma pro $0^n1^{n+1}2^{n+2}$). Oříškem bylo $i\not=j\not=k\not=i$.
Musíme se ještě vrátit ke vztahu konečných automatů a $\cal L_3$.
Cvičení 6
Nejprve jsme se věnovali vztahu konečných automatů a $\cal L_3$. Pak jsme se zabývali zásobníkovými automaty. Ukázali jsme jak simulovat automat přijímající prázdným zásobníkem pomocí automatu přijímajícího koncovým stavem. Pak jsme to zkoušeli naopak, a ukázalo se, že konstrukce vyžaduje nedeterminismus. V případě deterministických jazyků je přijímání prázdným zásobníkem „slabší“. Hlavní problém je v tom, že deterministické zásobníkové automaty přijímající prázdným zásobníkem mohou přijímat pouze bezprefixové jazyky. (Nezmínil jsem, že pokud bychom měli speciální znak pro konec slova, byla by síla automatů stejná.)
Pak jsme dále srovnávali výhody obou definic přijímání. Přijímání koncovým stavem se hodí hlavně v konstrukci kartézského součinu s regulárním jazykem. Přijímání prázdným zásobníkem se hodí hlavně pokud současně zredukujeme stavy. Ukázali jsme, že k nedeterministickému zásobníkovému automatu (přijímajícímu prázdným zásobníkem) existuje nedeterministický automat s jediným stavem, přijímající prázdným zásobníkem stejný jazyk.
Automat bez nutnosti evidvat stavy se hodí v konstrukci bezkontextové gramatiky generující jazyk přijímaný daným automatem. Naopak automat vzniklý přirozeným přepisem gramatiky nepotřebuje rozlišovat stavy.
Na konci cvičení jsme si hráli se „slovníkovými“ jazyky. Ukázali jsme, že existuje gramatika generující slova popisující překlad mezi slovy a zápisy v morseově abecedě. Šlo to tehdy, pokud byl překlad psaný „pozpátku“. Pomocí pumping lemma jsme ukázali, že bez převracení dostaneme jazyk, který není bezkontextový.
Končili jsme formulací jazyka pro překlad mezi osmičkovou a šestnáctkovou soustavou.
Cvičení 7
Vzhledem k tomu, že nijak nezaostáváme za přednáškou, zkusili jsme si kolektivně vyřešit jednu ze starších písemek.
Cvičení 8
Na dalším cvičení jsme se věnovali kontextovému tvaru $\cal L_1$ a $\cal L_0$ gramatik, pak jsme se ještě venovali vztahu nedeterministických Turingových strojů a $\cal L_1$ a $\cal L_0$ gramatik.
Trošku nejasností vzniklo při konstrukci monotónní gramatiky pro „lineárně omezené“ nedeterministické Turingovy stroje. Situaci by zjednodušilo, pokud by stroj měl zakázáno nejen přepisovat blank, ale i číst jej dvakrát po sobě. Jako záznam konfigurace stroje bychom zvolili řetězec, kde stav, písmenko pod hlavou a obě sousední písmenka jsou reprezentovány jediným neterminálem. Přechod na terminální řetězec by pak mohl být proveden nezkracujícím pravidlem.
Cvičení 9
Na úterním cvičení jsme psali písemku, všichni, kdo měli aspoň dva příklady dobře již mají zápočet v SIS.
Pokud by se někomu z pátečního cvičení udělalo 10.5.2019 či 17.5.2019 špatně, může přijít na náhradní písemku v úterý 7.5.2019. Neprošvihněte to.
Cvičení 10
Jak na úterním, tak na pátečním cvičení jsme psali písemku, všichni, kdo měli aspoň dva příklady dobře již mají zápočet v SIS.
Cvičení 11
Na předposledním pátečním cvičení jsme psali písemku, všichni, kdo měli aspoň dva příklady dobře již mají zápočet v SIS.
Cvičení 12
Na posledním cvičení jsme probírali písemku.