Vladan Majerech - NTIN071 Automaty a gramatiky
Last Modified: 10.3.2026
Index
zápočtové písemky, odkazy, cvičení 1, cvičení 2, cvičení 3, , cvičení 4
Zápočet je udělován za zápočtové písemky, které se konají na 3. a 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 dokázali, neostré inkluze ${\cal L}_{i+1}\subseteq {\cal L}_{i}$.
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_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. Pro $\cal L_2$ jsme pro DFS nad stromem odvození potřebovali nedeterministický zásobníkový automat. 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). 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é, ač jsem se nějak zmátl a psal jsem do zásobníku i malá písmena (přitom na základě zásobníkové abecedy definujeme neterminály) problém s potřebou „anihilace“ teminálů není, to co automat přečte gramatika má vygenerovat. 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 jsem ještě ukázal, že neplatí rovnosti ${\cal L}_{i+1}\not= {\cal L}_{i}$. Tedy pro $i=0$ jsem důkaz odkázal na základy složitosti a vyčíslitelnosti a u ostatních jsem naznačil jaké jsou rozdílové jazyky, dokázal pumping lemma a naznačil, že kvůli pumping lemma rozdílové nepatří do menších tříd (detaily byly přeskočeny). Co se týče standardizovaných tvarů, ukázali jsme jen standardizovatelnost bezkontextových $\cal L_2$ gramatik do Chomskiho normálního tvaru.
Cvičení 2
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á dané 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. Chvíli jsme se věnovali redukci automatů (ukázali jsme si, že v automatu pro gem jsme mohli tři dvojice stavů ztotožnit). Pak jsme pokračovali s tenisem a řešili jsme kdo vyhrál set. Přirozenou cestou jsme se dostali k tomu jak substituci jazyků k nimž máme konečné automaty implementovat jedním automatem.
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, a konstrukci vynechávající jedno konkrétní písmenko.
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.
Ke konci hodiny jsme si ještě vytvořili redukovaný automat přijímající čísla ve dvojkové soustavě bez úvodních nul, která jsou dělitelná šesti.
Cvičení 4
Začali jsme konstrukcí permutačního operátoru. Ukázalo se, že ne všechny jazykové konstrukce jsou realizovatelné konečnými automaty. V našem případě bychom konstrukci mohli využít ke konstrukci jazyka $a^nb^n$, což je nemožné. Ukázali jsme, že redukovaný automat pro $a^nb^n$ je nekonečný což souvisí s Nerodovou větou, načež jsme se začali věnovat pumping lematu 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 druhé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.