Vladan Majerech - NTIN071 Automaty a gramatiky

Last Modified: 7.3.2025

Valid HTML 4.01 Strict

Index

zápočtové písemky, odkazy, cvičení 1, cvičení 2, cvičení 3

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.