Vladan Majerech - NTIN071 Automaty a gramatiky

Last Modified: 17.4.2025

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

Zápočet je udělován za zápočtovou písemku, které se koná na 2. hodině od konce semestru. Na písemkce bude zadáno 6 příkladů ...


Zápočtové písemky

Příklady zápočtových písemek z daleké minulosti, kdy byly 4 příklady z nichž 2 správně vyřešené stačily na zápočet: 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í


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. Definovali jsme pojmy abeceda, slovo, jazyk, definovali jsme nedeterministický programovací jazyk „přepisovacích pravidel“, specifikací terminálů a neterminálů, počátečního stavu a deklarací náležení prázdného slova do jazyka jsme z toho vytvořili nedeterministický programovací jazyk gramatik a definovali jazyk, odpovídající konkrétní gramatice.

Následně jsme přidávali omezení na tvar přepisovacích pravidel gramatik a tím jsme rozškatulkovali gramatiky do tříd a definovali jim odpovídající Chomskiho třídy jazyků $\cal L_0,\ \dots, L_3$. U každé třídy jsme zároveň uvedli normalizovaný tvar gramatiky.

Pak jsme se věnovali nedeterministickým automatům, rozhodujícím, zda dané slovo je gramatikou generované (tedy patří do jejího jazyka). Pro $\cal L_3$ nám k tomu stačily konečné automaty charakterizované sjednocením nápisů na sledech mezi počátečními a koncovými vrcholy (ukázali jsme, že se nedeterminismu můžeme zbavit). Pro $\cal L_2$ jsme pro DFS nad stromem odvození potřebovali nedeterministický zásobníkový automat. Pro $\cal L_1$ a $\cal L_0$ jsme potřebovali přepisovatelnou pásku na níž se můžeme pohybovat oběma směry, tedy Turingovy stroje. V příadě $\cal L_1$ nám stačila páska velikosti vstupního slova. Ve všech případech jsem jen letmo naznačil, jak na základě stroje vytvořit gramatiku. (U zásobníkového automatu s jediným stavem to není těžké, ale ukázat ekvivalenci výpočetní síly vícestavových zásobníkových automatů s jednostavovými je netriviální).

Na konci hodiny jsme stihli ukázat neostré inkluze mezi třídami hierarchie (a doplnili definice gramatik o deklaraci prázdného slova, protože jinak by inkluze neplatily).

Na první hodině se mi nepodařilo zprovoznit ani mikrofon, ani zaměřit kameru na tabuli, takže jsme doufali v nahrávku z druhého cvičení. Tam se nám za pomoci SISALu za přestávku a dalších cca 15 minut podařilo mikrofon rozchodit (kamera byla snazší), takže jsem nahrávání spustil po cca 10 minutách cvičení. Bohužel na konci hodiny jsem místo tlačítka zastavit záznam viděl tlačítko spustit záznam. ... nejspíš probmém mezi myší a počítačem. Nahrávka na očekávaném místě nebyla. U dalších hodin už nahrávání bude snazší, nicméně výrazně méně užitečné.


Cvičení 2

První verzi cvičení jsme nahrávali. Nicméně fixy na tabuli si musíme domýšlet a nahraný zvuk je skutečně jen to, co jsem povídal já, a to co říkali studenti není slyšet vůbec.

Nejprve jsme pro zadané automaty zkoušeli zjistit, jaké přijímají jazyky. Pak jsme se zabývali jazykem automatu, o kterém jsme věděli jen, že má 4 stavy a přijímá krátké slovo tvořené opakováním písmene $a$. Otázkou bylo, zda z těchto informací můžeme pro jiná slova tvořená opakováním písmene $a$ určit, zda jej daný automat přijímá. Vzhledem k tomu, že se automat musel zacyklit, daly se najít délky slov, které automat přijímat musel.

Pak jsme se věnovali tenisu a automatům zjišťujícím, kdo vyhrál gem, kdo set a přirozenou cestou jsme se dostali k tomu jak substituci jazyků k nimž máme konečné automaty implementovat jedním automatem.

V závěru hodiny jsme se věnovali redukci automatů (ukázali jsme si, že v automatu pro gem jsme mohli tři dvojice stavů ztotožnit).


Cvičení 3

Věnovali jsme se jazykovým konstrukcím a jak z konečných automatů pro původní jazyky vytvořit automat přijímající jazyk definovaný příslušnou konstrukcí. Kromě standardních konstrukcí pro jazyk pozpátku, negaci jazyka, sjednocení či průnik, zřetězení, iterace, kvocienty, homomorfismy, inverzní homomorfismy, a substituce jsme probrali „zipovou“ konstrukci, konstrukci vkládající jedno konkrétní písmenko, konstrukci vynechávající jedno konkrétní písmenko a permutační konstruci. Ukázalo se, že permutační konstrukce nezachovává konečnost automatů, protože bychom pomocí ní a dalších konstrukcí, které zachovávají rozpoznatelnost konečnými automaty dokázali vytvořit jazyk $0^n1^n$, jehož redukovaný automat není konečný. U zipové konstrukce jsme udělali automat rozpoznávající jen slova sudé délky. Pro generování slov liché délky bychom museli být opatrnější s volbou koncových stavů.

Během konstrukcí jsme používali takové automaty, které se nám zrovna hodily (někdy deterministické, jindy nedeterministické s libovolnými slovy na hranách, občas bylo pohodlnější pracovat s automaty používajícími jediný počáteční a jediný koncový stav). Ukázali jsme si, jak ze všech takových automatů můžeme vytvořit deterministický automat, je-li potřeba.


Cvičení 4

Nejprve jsme se věnovali pumping lemmatu a jeho zobecnění, kde velikosti měříme v počtu podtržených písmenek vstupního slova. Zadal jsem dlouhodobý domácí úkol najít jazyk, takový, že pro něj i jeho doplněk platí podtrhávací pumping lemma a přitom nejde o jazyk rozpoznávaný konečným automatem.

Pak jsme se zabývali regulárními výrazy a jim odpovídajícími jazyky. To, že pro každý takový jazyk existuje odpovídající konečný automat vyplynulo z jazykových konstrukcí z minulé hodiny. Opačnou otázku, zda jazyk každého konečného automatu je možno popsat regulárním výrazem jsme ukázali zobecněním Floyd-Warshalova algoritmu. Ten jsme si vyzkoušeli na automatu z prvního cvičení. Ukázalo se, že se hodí rozmyslet si pořadí volených vrcholů pro Floyd-Warshal algoritmus i to, jaké mezivýsledky budeme v následujících fázích algoritmu potřebovat. Graficky tomu odpovídala postupná redukce vrcholů ukazovaná na přednášce.


Cvičení 5

Zkonstruovali a zredukovali jsme konečný automat rozpoznávající nezáporná celá binární čísla dělitelná šesti. Vyzkoušeli jsme podtrhávací pumping lemma na příkladu neregulárního jazyka na který obyčejné pumping lemma nestačí. (Samozřejmě pro protipříklad hledáme slovo z $L$ ...) Ukázali jsme ekvivalenci jazyků generovaných $\cal L_3$ gramatikami s jazyky rozpoznatelnými konečnými automaty a přitom jsme našli „normální formu“ $\cal L_3$ gramatik. Udělali jsme automat přijímající pozpátku jazyk automatu z druhého cvičení, determinizovali a redukovali jsme příslušný automat.


Cvičení 6

Věnovali jsme ze bezkontextovým gramatikám, převážně Chomskiho normální formě a pumping lemmatu. Na konci první verze cvičení jsme připomněli (z první hodiny) jak pomocí nedeterministického zásobníkového automatu (beze stavů), přijímajícího prázdným zásobníkem kontrolovat příslušnost slova do jazyka generovaného bezkontextovou gramatikou (nedeterministické procházení levé derivace, na zásobníku udržujeme inorder pořadí listů derivačního stromu kromě již zkontrolovaných terminálů).

Až na konci hodiny mi došlo, že jsme se vůbec nevěnovali dvoucestným konečným automatům a budeme to muset napravit příště.


Cvičení 7

Věnovali jsme se dvoucestným automatům, důkazu s přechodovými posloupnostmi, prefixovými relacemi a trochu i suffixovými relacemi. Zadal jsem dlouhodobý úkol týkající se dvoucestných automatů s kamínkem. U důkazu s přechodovými posloupnostmi jsem při testování návaznosti stavů neuvažoval možnost stání na místě. Tím by se test zkomplikoval, ale stále by byl proveditelný.

Na konci hodiny jsme ukázali, že nedeterministické zásobníkové automaty přijímající prázdným zásobníkem nepotřebují stavy, takže jim odpovídají bezkontextové gramatiky.


Cvičení 8

Video z neznámého důvodu obsahuje obraz jen v necelé čtvrtině plochy.

Věnovali jsme se (ne)ekvivalencím různých definic zásobníkových automatů. Pak jsme se věnovali slovníkovému jazyku pro převod mezi číselnými soustavami (s různými endiány). Na nahrávaném cvičení jsme zapomněli ukázat gramatiku, která generuje daný jazyk v případě, kdy se jedná o jazyk bezkontextový. Na konci cvičení jsme se začali věnovat normalizaci tvaru monotónních gramatik.


Cvičení 9

Věnovali jsme se $\cal L_0$ a $\cal L_1$. Nejprve jsme dokončili převod monotónních gramatik na monotónní kontextovou normální formu, následně obecných gramatik na obecnou kontextovou formu. Pak jsme diskutovali jak na základě obecné či $\cal L_1$ gramatiky vytvořit nedeterministický turingův stroj, který testuje zda dané slovo je gramatikou generované. (U $\cal L_1$ gramatik se postupně použitá délka pásky zkracovala (nikdy se neprodlužovala)). Následně jsme se bavili o tom jak na základě (nedeterministického) Turingova stroje vytvořit gramatiku, která generuje právě slova, která daný stroj přijímá. U strojů, které nikdy neprodlužují použitou délku pásky nám vznikla monotónní gramatika. Nejspíš bychom chtěli korespondenci i mezi stroji, které neprodlužují použitou část pracovní pásky oproti délce vstupního slova, ale mohou pásku zkrátit a pak méně prodloužit. Nejspíš by trikem bylo nezkracovat pracovní pásku průběžně, ale nechat to až na fázi závěrečného smazání pracovní pásky (transformace programu Turingova stroje), pak by nám i v takovém případě vznikla monotónní gramatika.

Pak jsme se věnovali existenci jazyků, pro které neexistuje gramatika, která by je generovala (stroj, který by je rozpoznával). Početní argument jsme podpořili důkazem nespočetnosti (odrazili jsme se od Cantorovy diagonalizace intervalu reálných čísel) a použili zjednodušenou variantu. Uvědolmili, jsme si, že řádky mohou reprezentovat jak všechny gramatiky, tak všechny programy. Ještě jsme mírně formalizovali univerzální jazyk a popis diagonálního jazyka pomocí univerzálního jazyka.

Následně jsem (na nahrávaném cvičení) naznačil Postův korespondenční problém a schéma jak v případě inicializované varianty můžeme zkonstruovat zadání simulující obecný jednopáskový stroj na určeném vstupu. Také jsem naznačil jak pomocí neinicializované varianty odsimulovat inicializovanou variantu problému.

Ve zbylých 20 minutách jsem naznačoval bez důkazů výsledky (teorie) složitosti, z nichž plyne, že existuje jazyk patřící do $\cal L_0\setminus L_1$. Jednalo se o větu o hierarchii pro nedeterministický prostor. Jednodušší důkaz má věta o hierarchii pro deterministický prostor, pak ale potřebujeme navíc i Savičovu větu. Všechny tyto použité věty mají v předpokladech prostorovou konstruovatelnost. Naznačil jsem, že existují i funkce, které nejsou prostorově konstruovatelné. O Ramseově funkci to jen tušíme, ale neumíme dokázat, zatímco Borodinova věta o mezerách konstruuje funkci, která pokud by byla konstruovatelná, pak bychom pomocí ní získali protipříklad věty o hierarchii.