Vladan Majerech - NTIN071 Automaty a gramatiky

Last Modified: 20.5.2020

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.

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). 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í jsem oznámil podmínky zápočtu a následně jsem udělal overview toho, co se bude dít v průběhu semestru. Ke konci hodiny jsme o třech daných konečných automatech zkoušeli zjistit, jaký přijímají jazyk.

Cvičení 2

Na cvičení jsme si povídali o Myhill-Nerodově větě, 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.

Řešili jsme 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.

Pak jsme si ještě hráli s automatem počítajícím skóre v tenisovém gemu. Naznačili jsme, algoritmus redukce (jak z přednášky zjišťující nekompatibilní dvojice stavů, tak alternativní, zjemňující rozklad stavů do tříd ekvivalence. Redukci jsme nestihli dokončit. Použití automatu pro automat počítající tenisový set (bez tiebreaku) jsme taky načrtli s tím, že takové konstrukci v budoucnu budeme říkat substituce.

Redukci nekonečného automatu pro jazyk $0^n1^n$ jsme taky nedokončili, nicméně nepřijímání konečným automatem jsme (bez použití pumping lemma) dokázali. (Ukázali jsme, že pro libovolné $n$ potřebuje automat více než $n$ stavů.)

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 se učili programovat konečné automaty jako stavebnice. Používali jsme konečné automaty jako reprezentanty odpovídajících jayzků a řešili jak promítnout různé jazykové konstrukce v konstrukci automatů.

Začali jsme $L^R$ jazykem slov pozpátku. Přirozeně jsme tak ve skládačce přešli z deterministických na nedetrministické konečné automaty. Ukázali jsme jak z nedeterministických automatů vytvořit automat deterministický.

Pokračovali jsme množinovými operacemi nad jazyky (sjednocení, průnik, asymetrické, symetrické rozdíly). Ukázalo se, že současný běh dvou deterministických automatů a kontrola který automat skončí v koncovém stavu nám dokáže říct, zda slovo patří do jazyka. No a současný běh dvou automatů snadno odsimulujeme jejich kartézským součinem.

Následovala zřetězení a iterace. Tam se ukázalo přirozené použít $\lambda$ přechody. Opět jsme si ukázali, jak k takovému automatu najít deterministickou verzi.

Pak jsme zkoušeli další operace jako je vynechání všech písmenek jednoho druhu (nahrazení hran daného písmene $\lambda$ přechody, což je speciální případ homomorfismu), následně jsme zkoušeli přidávat či ubírat jeden výskyt daného písmene (hodilo se pamatovat si bit informace, zda ke změně již došlo), zkoušeli jazyk modifikovaný přetržením slov a jejich slepením v opačném pořadí (pro každý stav, ve kterém je možno přetrhnout, jiná verze automatu resp. jiná souřadnice v kartézském součinu). Zkusili jsme i permutační operátor, ale ukázalo se, že takovou konstrukci konečným automatem realizovat nejde (uměli bychom zkonstruovat automat pro $0^n1^n$).

Stihli jsme i homomorfismus, inversní homomorfismus a substituci (kterou jsme si tenisovým automatem již připravili na minulé hodině).

Původní záměr, vytvářet jazykovými konstrukcemi automaty, na kterých budeme zkoušet redukce automatu příliš nevyšel.

Cvičení 4

Cvičení se kvůli epidemii Covid-19 v přítomnosti studentů nekonalo. Plánem bylo pokračovat v jazykových konstrukcích, chybí nám především levý a pravý kvocient $L_2\backslash L_1=\{v\mid u\in L_2\wedge uv\in L_1\}$ resp. $L_1/L_2=\{u\mid v\in L_2\wedge uv\in L_1\}$. Druhou konstrukci je snadné udělat pomocí první a $L^R$. U té první je důležité uvědomit si, jak se chovají příslušné „pravé kongruence“. Zjistíme, že stejně jako u $L_1$. Použít tedy $L_1$ jako základ konstrukce je dobrý nápad. Jen je potřeba zjistit množinu počátečních stavů. Ke zjištění množiny počátečních stavů je potřeba zjistit, v kterých stavech se $L_1$ může nacházet, je-li $L_2$ v nějakém koncovém stavu. „Pustíme“ je tedy současně a „budeme sledovat, co se stane“.

Dalším plánem bylo probrat vztah regulárních výrazů a jim odpovídajících jazyků a jazyků přijímaných konečnými automaty (Kleeneho věta). Regulární výrazy obsahují $\lambda$ pro označení prázdného slova, písmena abecedy a kromě toho symboly pro iterace $^*$, $^+$, zřetězení $\cdot$ (vynecháváme) a sjednocení $+$. Kvůli pořadí vyhodnocování operátorů je jsou definovány priority (ve zde uvedeném pořadí) a zavedeny závorky.

Vzhledem k tomu, že pro prázdné slovo i každé písmeno abecedy jsme schopni sestavit konečný automat, který přijímá odpovídající jazyk, a navíc jsme již probrali jazykové konstrukce jak příslušné operace na jazycích implementovat pomocí modifikace automatů, je jasné, že pro jazyky odpovídající regulárním výrazům jsme schopni vytvořit konečné automaty, které je rozpoznávají.

Opačný vztah je mnohem zajímavější. Je možno jazyk libovolného konečného automatu popsat regulárním výrazem? Vzhledem k Floyd-Warshalově algoritmu to problém není. Konstrukci příslušného regulárního jazyka pro náš oblíbený třístavový automat bylo plánováno si procvičit. Správné pořadí redukce stavů a nepočítání nepotřebných mezivýsledků výrazně zefektivňuje postup. Typicky při prvním pokusu člověk postupuje velice neefektivně. Při získání výsledku není tak těžké zrekapitulovat, jaké mezivýsledky jsme potřebovali. Většina studentů ale nepostupuje tak, že by si nejprve představila jak dojde k výsledku, udělala si „závislostní strom“ a počítání nepotřebných mezivýsledků přeskočila.

O moc víc bychom asi na cvičení nestihli. Za domácí úkol (dělám to nerad) mi pošlete regulární výraz popisující jazyk našeho oblíbeného automatu (stavy 1,S,0, přechody nulou doprava jak to jde, jedničkou doleva jak to jde a S je počáteční i koncový). Preferovaný je výše naznačený postup. Pokud máte nějaké nejasnosti, tak se zamyšlete případně zeptejte.

Cvičení 5

Cvičení proběhlo formou videokonference, tedy kameru jsem měl zapnutou jen já, studenti občas zapínali mikrofony. Vzhledem k tomu, že z konečných automatů již máme probráno téměř vše (jazykové konstrukce, ekvivalence s regulárními výrazy a jim odpovídajícími jazyky), zbývala nám poslední zajímavost a tou jsou dvoucestné automaty (nevěnovali jsme se Moorovým a Mealyho strojům s výjimkou automatu na tenis, u něhož byla zajímavá především varianta hlásící mezivýsledky).

Cvičení probíhalo tak, že jsem prozradil princip jedné konstrukce (prefixová přechodová funkce a množina stavů ve které se může automat v daném místě pásky nacházet). Pak jsem postupně konkretizoval otázky, které je potřeba si klást, abychom konstrukci zkonkretizovali. (Máme-li na vstupu slovo $\alpha X\beta$ a čteme políčko s písmenem $X$, prefixová funkce pro každý stav $q$ vrací množinu stavů, v níž se můžeme vrátit na políčko s písmenem $X$, pokud se ve stavu $q$ nalézáme na konci slova $\alpha$.) Během hodiny se nám to podařilo zkonkretizovat a snad většina pochopila jak daná konstrukce funguje. Důležitá při přepočtu z $\delta_\alpha$ na $\delta_{\alpha X}$ byla množina stavů $M(q)$, do nichž se z $q$ můžeme dostat před tím, než opustíme $X$ doprava. I v příadě deterministického dvoucestného automatu nám může vyjít množina $M(q)$ víceprvková. Co se týče $\delta_{\alpha X}(q)$, tak výsledná množina může vyjít více než jednoprvková pouze v případě že převádíme nedeterministický dvoucestný automat. Známe-li množinu stavů $M_{\alpha}$, ve která se můžeme nacházet na políčku s písmenem $X$, tak sjednocením aplikací $\delta%{\alpha X}$ na jednotlivé stavy dostaneme množinu stavů $M_{\alpha X}$ do kterých se můžeme při prvním výstupu z $\alpha X$.

Běžně na hodině stíháme projít i důkaz s přechodovými posloupnostmi, i důkaz založený na nedeterministické simulaci pomocí sufixové přechodové funkce.

Co se týče simulace pomocí sufixové přechodové funkce, zákeřné je, že „pevný bod“ dostaneme až na pravém konci vstupního slova, kde víme, že sufixová funkce musí být prázdná. Nezbyde nám než vytvořit nedeterministický automat. Sám o sobě už bude mít extrémně velký počet stavů, takže jeho determinizací bychom očekávali ještě další exponenciální nárůst. (Ale vzhledem k tomu, že redukovaný automat výjde vždy stejně, tak to asi tak strašné nakonec nebude.) Jedná se o náročné cvičení na uvědomění si toho, jak může být použit nedeterministmus v programování. Pravidelně tuto možnost uvádím, protože se jedná o krok potřebný k vyřešení dlouhodobého domácího úkolu: Dokažte, že dvoucestný automat s kamínkem rozpoznává pouze jazyky rozpornávané obyčejnými deterministickými konečnými automaty. (No a kamínek je dočasná značka na políčku, kterou jsme schopni položit, testovat a případně zvednout, nesmíme mít ale dvě značky. Automat ví, zda značku položil, či naopak ji má k dispozici k položení.)

Technika přechodových posloupností probíraná na přednášce a neprobraná na cvičení ... vyžaduje pracovat jen s „v inkluzi nejkratšími“ přijímacími výpočty. To nám umožňuje z nekonečně dlouhých posloupností vybrat jen ty, kde se stav pod písmenkem $X$ neopakuje. Tím dostaneme jen konečně mnoho potenciálních stavů. Zákeřnost při počítání přechodové funkce je, že je daleko jednodušší než přemýšlet, kam je možno z daného maxistavu přejít při čtení daného písmene, rozhodnout zda je možno při čtení daného písmene přejít z maxiastavu A do maxistavu B. Ani tento test není nejjednodušší, je potřeba ze všech možných navázání dvou přechodových posloupností otestovat všechny, zda alespoň jedna z nich je přípustná.

Cvičení 6

Cvičili jsme "teorii" bezkontextových gramatik, podařilo se nám ukázat, že až na deklaraci příslušnosti prázdného slova do jazyka jsme každou bezkontextovou gramatiku schopni převést do Chomskiho normálního tvaru, tedy, že pravé strany obsahují buď jediný terminál disjunktně nebo právě dva neterminály.

Následně jsme použitím Chomskiho normální formy s $n$ neterminály ukázali (podtrhávací) pumping lemma pro bezkontextové jazyky: Máme-li aspoň $2^n+1$ podtržených písmen ve vygenerovaném terminálním slově, tak v derivačním stromě existuje podstrom s podrtrženými listy s nejdelší větví aspoň $n+1$ neterminálů. Proto se na nejdelší cestě nějaký neterminál musí zopakovat. Vezmeme odspoda první zopakovaný neterminál (jen co se týče vrcholů podstromu). Nechť jím je $X$. Tím se nám úseky slova rozpadnou na $x_1$, $x_2$, $x_3$, $x_4$, $x_5$, přičemž podle rozbočení v horním $X$ máme garantováno buď v $x_2$ nebo v $x_4$ podtržené písmenko. Protože šlo o první zopakování na nejdelší cestě, máme garantováno, že $x_2x_3x_4$ má nejvýš $2^{n+1}$ podtržených písmenek. No a je jasné, že každé $x_1x_2^kx_3x_4^kx_5$ je generované taky (pro $k$ celé nezáporné).

Za domácí úkol je (neposílat mailem, jen rozmyslet): Dokažte, že $L=\{a^ib^jc^k\mid i\not=j\not=k\not=i\}$ není bezkontextový jazyk.

Cvičení 7

Probrali jsme zásobníkové automaty, varianty přijímání koncovým stavem i prázdným zásobníkem a jejich vzájemné transformace, pak jsme ukázali, jak se u nedeterministického zásobníkového automatu přijímajícího prázdným zásobníkem můžeme zbavit stavů (redukovat je na jeden). To jsme následně použili v důkazu toho že každý jazyk přijímaný nedeterministickým zásobníkovým automatem je možno vygenerovat bezkontextovou gramatikou. Stejně tak jsme pro gramatiku v Chomskiho normální formě našli jednostavový automat, který přijímá gramatikou generovaný jazyk.

Na konci hodiny jsme se věnovali domácímu úkolu z minula a s použitím podtrhávacího lemma a násobku nejmenšího společného násobku možných period (například $n!$, $2n!$) jsme našli protipříklad.

Cvičení 8

Cvičili jsme příklady na bezkontextové gramatiky a jejich vztah k regulárním a monotónním gramatikám. Uvědomili jsme si, že pro jednopísmenné abecedy jazyky generované regulárními a bezkontextovými gramatikami splývají. Pro vícepísmenné abecedy například jazyk palindromů patří do bezkontextových, ale ne do regulárních. Používali jsme pumping lemma pro obě třídy.

Následně jsme zkoumali slovníkové jazyky pro morseovku a překlad mezi číselnými soustavami. jen pokud byly pravé starny převrácené, měly bezkontextové gramatiky šanci na úspěch. V případě překladu mezi číselnými soustavami bylo potřeba spočítat, jak se pumpováním mění číslo na každé straně rovnosti. Hodilo se posčítat příslušnou geometrickou řadu, abychom odvodili nutnou a postačující podmínku pro základy číselných soustav, pro které je výsledný jazyk bezkontextový. Jazyk byl vždy generovaný monotónní gramatikou, která postupně přičítala jedničku na obou stranách.

Cvičení 9

Věnovali jsme se monotónním gramatikám a hlavně speciálnímu kontextovému tvaru jak pro monotónní gramatiky, tak pro gramatiky typu 0.

Cvičení 10

Nejprve jsme se na chvíli vrátili k deterministickým zásobníkovým automatům, pak jsme si probrali domácí úkol a vyzkoušeli jednu ze starých písemek.

Cvičení 11

Udvodili jsme, jak jazyk generovaný obecnou gramatikou dokáže rozpoznávat nedeterministický jednopáskový Turingův stroj. Odvodili jsme, jak pro jazyk rozpoznávaný (nedeterministickým) jednopáskovým Turingovým strojem vytvořit obecnou gramatiku, která jej generuje. Odvodilli jsme, jak jednopáskovým Turingovým strojem odsimulovat stroj vícepáskový. Ukázal jsem jak vícepáskovým deterministickým strojem odsimulovat nedeterministický Turingův stroj.

Cvičení 12

Psali jsme písemku, Byla zadávána e-mailem. Písemka je opravená, zápočty uděleny. Pro ty, co dostali zápočet, příští týden zadání generovat nebudu. Kdo by se nudil, může zalistovat v historických písemkách.

Cvičení 13

Psali jsme písemku, Byla zadávána e-mailem. Písemka je opravená, zápočty uděleny.

Cvičení 14

Kromě povídání o písemkách a vysvětlení konstrukce pumpovatelných nebezkontextových jazyků jsme se věnovali nespočetnosti jazyků a postově korespondenčnímu problému.

Ti co stále ještě mají zájem získat zápočet mi napíší e-mail, já jim přidělím seznam malých přirozených čísel, každému číslu odpovídají příklady, jejichž řešení očekávám e-mailem (vždy s uvedením $x$). Pokud v řešení najdu chybu, přestanu kontrolovat, oznámím, která zadání jsou vyřešena OK (čímž se může seznam zkrátit), navíc oznámím nové číslo, čímž se seznam následně prodlouží. Pokud v řešení chybu nenajdu, oznámím to a seznam se zkrátí. Prázdný seznam znamená zápočet.

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