Vladan Majerech - NTIN071 Automaty a gramatiky

Last Modified: 28.5.2018

Valid HTML 4.01 Strict

Index

zápočtové písemky, 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

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í

Cvičení 1

Na prvním cvičení jsem „rekapituloval“ co je obsahem předmětu Automaty a gramatiky.
Popsal jsem, co jsou systémy přepisovacích pravidel a jimi generované jazyky.
Zdůvodnil jsem, jak se zvýší výpočetní síla rozdělením abecedy na terminály ($V_T$) a neterminály ($V_N$), čímž jsme se dostali ke gramatikám.
Následně jsem popsal omezení gramatik vedoucí k definicím tříd Chomskiho hierarchie ${\cal L}_0$ (bez), ${\cal L}_1$(monotónní), ${\cal L}_2$(bezkontextové), ${\cal L}_3$(regulární, s nejvýš jedním neterminálem na pravém konci).
Stihli sme ukázat, platnost neostrých inkluzí ${\cal L}_{i}\supseteq {\cal L}_{i+1}$ mezi těmito třídami jazyků. Jediná netrivialita byla mezi druhou a první třídou, aby inkluze platila, je u druhé třídy v definici gramatiky potřeba bit informace, zda prázdné slovo do jazyka patří. Monotónní gramatiky jinak nemají prostředek k vygenerování prázdného slova.
Na konci jsem popsal akceptory odpovídající jednotlivým stupňům hierarchie. (Od nejvyšších čísel: konečné automaty, zásobníkové automaty, Turingovy stroje s páskou omezenou velikostí vstupu, Turingovy stroje bez omezení). Všechny akceptory byly nedeterministické, což přirozeně odpovídá nedeterminismu v definici jayzků generovaných přepisovacími pravidly. V případě konečných automatů a Turingových strojů je možno nedeterminismus odstranit, u zásobníkových automatů ne.
U gramatik typu ${\cal L}_0$ a ${\cal L}_1$ jsem uvedl standardizovaný kontextový tvar. Uvedl jsem také, že inkluze ${\cal L}_{i}\supset {\cal L}_{i+1}$ mezi třídami Chomskiho hierarchie jsou ostré.
Kromě důkazu neostrých inkluzí bylo naznačeno proč konečné automaty dokáží rozpoznat to, co regulární gramatiky generují. Opačná inkluze dokazována nebyla. Jiná tvrzení o Chomskiho hierarchii dokazována nebyla.
Co zaznělo na úvodním cvičení určitě ještě zazní na přednáškách a/či dalších cvičeních.

Cvičení 2

Na druhém cvičení jsme ignorovali Nerodovu větu a věnovali jsme se čtení cizích programů. U nekomentovaných to šlo snadno v triviálních případech, ale u dvou třístavových automatů jsme dlouho tápali. Jedním z nich byl automat s "resety", druhým z nich byl automat testující děllitelnost 3mi ve dvojkové soustavě. U toho druhého jsme dostali zajímavou charakterizaci dělitelnosti (škrtneme úvodní nulu, poodstraňujeme dvojice stejných sousedních čísel a pokud nám zbyde slovo délky 5 či 6 mod 6 = počet jedniček dělitelný třemi, bylo číslo dělitelné). Pak jsem ukázal, že u komentovaných programů je mnohem snazší zkontrolovat co dělají (vhodným komentářem je popis jazyků, kterými jsou jednotlivé stavy dosažitelné). Pak jsme si zkusili dva automaty sami zkonstruovat (dělitelnost 4mi a tenisový game) a ukázali jsme si algoritmus redukce automatu.

Cvičení 3

Na třetím cvičení jsme se zabývali tím co pro jazyk vyplývá z konečnosti automatu. Ze zopakování stavu na dlouhém přijímacím sledu v grafu automatu vyplývá existence dalších přijímacích sledů. Zformulovali a dokázali jsme podtrhávací variantu lemmatu: $\forall L$ rozpoznávaný konečným automatem $\exists\,n\,\forall w\mid |w|_{\_}>n\,\exists\, u_1,\,u_2,\,u_3$, kde $w=u_1u_2u_3$ a $|u_1u_2|_{\_}\le n$, $|u_2|_{\_}>0$ a $\forall i\ge 0\,u_1u_2^iu_3\in L$.

Za dlouhodobý dobrovolný domácí úkol je otázka, zda pokud pro $L$ i jeho doplněk platí podtrhávací pumping lemma, tak je $L$ (i jeho doplněk) rozpoznatelný konečným automatem.

Ukázali jsme si, jak pomocí podtrhávacího lemma dokázat neregularitu jazyka $L=a^*b^ic^id^*\cup b^*c^*d^*\cup a^*b^*c^*$, na což normální pumping lemma nestačí. Zabývali jsme se nepřijímáním $0^n1^n$ konečným automatem jak konstrukcí redukovaného nekonečného automatu (Nerodova věta, ukázka že konečný počet stavů nestačí). Pak jsme se věnovali chvilku $a^{n^2}$, a pak úloze na nejmenší společný násobek související s konečnými automaty nad jednopísmennou abecedou. (Počet $n+1\choose 2$ platí pro počet automatů s jedniným přijímajícím stavem pro $a^5$. Pokud by mohlo být více přijímacích stavů, bude jejich počet před redukcí násoben $2^n$, ale na kolik se zmenší redukcí netuším. Tedy těch $n+1\choose 2$ by se redukcí zmenšilo na $n$, netuším, co by redukce udělala pro všechny možné množiny koncových stavů.)

Ke konci hodiny jsme se začali věnovat jazykovým konstrukcím. Ukázali jsme jak přijímat jazyk slov jiného jazyka pozpátku. Při té příležitosti jsme se naučili determinizovat nedeterministický automat. Odhadli jsme, jak se může počet stavů redukovaného automatu pro jazyky $L$ a $L^R$ lišit. Pak jsme se zabývali sjednocením a průnikem jazyků. (V druhém případě jsme použili kartézský součin, v prvním jsme si to neuvědomili.)

Cvičení 4

Na čtvrtém cvičení jsme se dále zabývali operacemi nad jazyky. Popsali jsme homomorfisus, substituci (tenisový set) a inversní homomorfismus a přišli jsme na to, jak z automatů pro původní jazyky udělat automat pro výsledný jazyk. Popsali jsme zřetězení a iterace. Hráli jsme si s vložením a vypuštěním jednoho písmene „a” ze slov jazyka (a evidovali konstantní množství informace duplikováním původního grafu automatu.) Pohráli jsme si i s jayzkovou konstrukcí, kde každé sudé písmeno slova je prohozeno s písmenem předchozím. Jako poslední jsme se zabývali kvocientem. Konstrukci automatu pro jeden z nich jsme si rozmysleli, k druhému kvocientu jsme se nedostali. (Na středečním cvičení jsme se navíc zabývali i konstrukci $\{uvw\mid uvw\in L_1 \wedge v\in L_2\}$.)

Cvičení 5

Na pondělním cvičení jsme dodělali konstrukci $\{uvw\mid uvw\in L_1 \wedge v\in L_2\}$. Další konstrukci, kterou jsme udělali byla $\{uvw\mid uv\in L_1 \wedge vw\in L_2\}$. Pak jsme se zabývali Kleeneho větou. Implikace jak pro regulární výraz najít stroj plynula z již probíraných jazykových konstrukcí. Implikace jak pro stroj najít regulární výraz/jazyk plynula z Floyd-Warshalova algoritmu. Na jednoum automatu jsme aplikací algoritmu příslušný jazyk našli. Poučením z chyb bylo, že nepotřebujeme počítat jazyky pro přechody mezi libovolnými stavy, ale stačí nám z počátečních do koncových stavů. Pokud tedy vrchol již je ve sledech zahrnut, můžeme jeho řádek odstranit (není-li počáteční) a jeho sloupec můžeme odstranit (není-li koncový). Snažíme se vrcholy přidávat tak abychom řádky resp. sloupce odstraňovali co nejrychleji. Na konci hodiny jsem naznačil existenci dvoucestných automatů a jejich možný převod na normální automat.

Cvičení 6

Na začátku cvičení jsem se krátce vrátil k dvoucestným automatům a naznačil jsem konstrukci využívající sufixové návratové přechodové funkce. Na rozdíl od konstrukce využívající prefixové návratové přechodové funkce (probírané na konci minulého cvičení) tato konstrukce potřebuje nedeterministmus.

Jako dlouhodobý domácí úkol jsem zadal otázku zda dvoucestné automaty s jedním (resp. dvěmi) kamínky rozpoznávají stejné jazyky jako konečné automaty.

Ve zbytku hodiny jsme konstruovali redukovaný automat rozpoznávající slova nad abecedou ${a,b}$ obsahující $abba$ jako podslovo a neobsahující $baab$ jako podslovo.

Cvičení 7

Na sedmém cvičení jsme se zabývali zásobníkovými automaty a bezkontextovými gramatikami. Nejprve jsme si uvědomili, že u nedeterministických zásobníkových automatů je jedno, zda pracujeme v modelu přijímání koncovým stavem nebo prázdným zásobníkem. Naopak u deterministických zásobníkových automatů je přijímání koncovým stavem silnější než přijímání prázdným zásobníkem. (Jedna simulace je bez problémů, druhá vyžaduje nedeterministické rozhodnutí. Navíc přijímání prázdným zásobníkem vylučuje aby v jazyku bylo nějaké slovo prefixem jiného, takže existují regulární jazyky, na něž deterministický zásobníkový automat přijímající prázdným zásobníkem nestačí. Na regulární jazyky deterministické automaty přijímající koncovým stavem stačí (na zásobník ukládají vždy startovací symbol)).

Následně jsme se věnovali nedeterministickým automatům přijímajícím prázdným zásobníkem. Ukázali jsme, že zásobník může být použit k redukci počtu stavů na jeden. (Museli jsme evidovat jak stav ve kterém jsme, tak stav, do kterého klesneme až poklesne zásobník. To musíme nedeterministicky predikovat a při poklesu kontrolovat.) Pro jednostavový nedeterministický zásobníkový automat je pak již ekvivalence přijímaného jazyka s jazykem generovaným odpovídající bezkontextovou gramatikou přirozená. A stejně tak pro bezkontextovou gramatiku je ekvivalence gramatikou generovaného jazyka s jazykem rozpoznávaným odpovídajícím jednostavovým nedeterministickým zásobníkovým automatem přirozená.

Dále jsme se zabývali Chomskiho normální formou a algoritmem převodu obecné bezkontextové gramatiky do této formy.

Pokračovali jsme zavedením značení, které je nazýváno derivačním stromem a přirozeně nám vyšel vztah mezi minimální hloubkou derivačního stromu pro slovo dané délky pro gramatiku v Chomskiho formě. Důsledkem bylo opakování neterminálu na nějaké větvi v odvození dostatečně dlouhého slova a důsledek ve formě pumping lemma pro bezkontextové gramatiky.

Ukázali jsme jak pomocí pumping lemma dokázat to že $a^nb^nc^n$ není bezkontextový, ale na $a^ib^jc^k$, kde $i\not=j\not=k\not=i$ nám lemma nestačilo. Odvodili jsme proto i podtrhávací pumping lemma pro bezkontextové jazyky a podtržením právě všech $a$ v $a^nb^{n+n!}c^{n+2n!}$ jsme bezkontextovost daného jazyka vyvrátili.

Cvičení 8

Na osmém cvičení jsme se věnovali příkladu popište reglárním výrazem jazyk slov nad abecedou $\{0,1\}$, kde za každou $1$ následuje $0$ a nikde nejsou tři $0$ za sebou.

Zkonstruovali jsme automat pro tento jazyk (kartézský součin), pak jsme Floyd-Warshalovým algoritmem výraz zkonstruovali. (Dávali jsme si pozor, abychom počítali pouze hodnoty, které budeme dále potřebovat.) Já jsme předtím napsal “kvalifikovaný odhad„, jak by regulární výraz mohl vypadat.

Regulární výrazy vypadali jinak, tak jsme zkusili zjistit jestli generují stejný jazyk. Zkonstruovali jsme pro ně labda automat, který jsme determinizovali a redukovali. První z nich vyšel stejně jako automat pro daný jazyk, druhý automat vyšel jinak. To už byl konec hodiny a mírně jsme přetáhli. Druhý automat negeneroval $00$, což vedlo k odhalení chyby, kdy nám v automatu chyběl jeden lambda přechod. Po opravě chyby a nové determinizaci se již automat redukoval na již známý automat. (Průběh pondělního cvičení se jen nepatrně lišil.)

Cvičení 9

Na devátém cvičení jsme si nejprve připomněli, že na přednášce byla Chomskiho normální forma, probráno pumping lemma pro bezkontextové jazyky a ukázáno, že jazyk slov $a^kb^kc^k$ není bezkontextový. Zmínil jsem se o Greibachové normální formě a o tom, jak by v případě vždy různých terminálů na začátku pravé strany bylo možno rozpoznávat slova jazyka deterministickým zásobníkovým automatem. Chtěl jsem ukázat, že ne každou bezkonetextovou gramatiku je možno převést na gramatiku s touto vlastností. Začali jsme se proto zabývat jazykem $a^kb^lc^m$, kde buď $k=l$, nebo $l=m$. Gramatiku jsme zkonstruovali po částech: Nejprve jsme vytvořili gramatiku typu 3 generující $c^m$, potom gramatiku typu 2 generujjící $a^kb^k$. Pak jsem ukázali, jak z bezkontextových gramatik pro jayzky $L_1$ a $L_2$ vytvořit gramatiku pro jayzk $L_1L_2$. Tím jsme dokončili konstrukci gramatiky pro $a^kb^kc^m$. Obdobně bychom mohli zkonstruovat gramatiku pro jazyk $a^kb^mc^m$.

Další konstrukci, kterou jsme odvodili byla konstrukce která z gramatik pro jazyky $L_1$, $L_2$ vytvoří gramatiku pro jejich sjednocení.

Další přirozenou otázkou je, jak je možno z bezkontexových gramatik pro jazyky $L_1$ a $L_2$ vytvořit bezkontexových gramatiku pro jayzk $L_1\cap L_2$. V našem případě bychom dostali bezkontextovou gramatiku pro jazyk $a^kb^kc^k$, což nejde. Obecná konstrukce pro průnik dvou bezkontextových jazyků tedy nemůže existovat.

Ve zbytku cvičení jsme vytvořili monotónní gramatiku pro $a^kb^kc^k$ a pak jsme se zabývali kontextovou normální formou pro monotónní gramatiky. Zatím jsme si rozmysleli pouze konstrukci, jak nahradit pravidlo $AB\to CD$ (na pondělním cvičení jsme se dostali dál).

Cvičení 10

Na desátém středečním cvičení a na devátém pondělním jsme se zabývali kontextovými normálními formami monotónních gramatik a gramatik typu 0. Na středečním jsme si povídali i o rozpoznávání slov generovaných monotónními a obecnými gramatikami pomocí nedeterministických Turingových strojů (v prvním případě s páskami omezenými velikostí vstupu). V případě obecných gramatik jsem naznačil, jak je možno stroj determinizovat. Taky jsme hovořili o možnosti simulovat Turingovy stroje gramatikami.

Cvičení 11

Na desátém pondělním a jedenáctém středečním cvičení jsme psali písemku.

Cvičení 12

Na jedenáctém pondělním a dvanáctém středečním cvičení jsme psali druhou písemku.

Cvičení 13

Na posledním cvičení jsme rozebírali písemky. Perlička z pondělního cvičení: V písemce byl definován normální kontextový tvar, kde kontext „přehazoval“ ($\alpha X\beta\to\alpha\beta\gamma$). Úlohou bylo dokázat, že jde normální tvar obecných gramatik. Nebylo to tak zamýšleno, ale i tento tvar by mohl být používán jako normální tvar.

Pak jsme řešili, co s těmi, kteří si zápočet nezasloužili. Jejich úkol je poslat mi e-mail, v odpovědi dostanou několik celých čísel. Každému číslu odpovídají dva příklady. E-mailem odevzdané správné řešení obou příkladů vede k vyřešení daného čísla, špatně odevzdané řešení příkladu vede k „zisku“ dalšího čísla. Ve chvíli, kdy má student vyřešena všechna získaná čísla, dostane zápočet.

Příklady pro číslo $k$: