IB102 úkol 7, příklad 1 Odevzdání: 5. 11. 2018 Jméno: UČO: list učo body Oblast strojově snímaných informací. Své učo a číslo listu vyplňte zleva dle vzoru číslic. Jinak do této oblasti nezasahujte. 1. [2 body] Nechť Σ = {l, u, f, o, g}. Navrhněte algoritmus, který pro zadaný NFA A pracující s abecedou Σ zkontroluje zamykání zámku v jednotlivých slovech akceptovaných automatem A. Kontrolu budeme provádět na slovech, v nichž l představuje akci „zamknout zámek“ (lock) a u představuje akci „odemknout zámek“ (unlock), písmena f, g a o představují akce, které na zámek nemají vliv. Chceme kontrolovat, že • po každém zamknutí dojde k odemknutí zámku, • nepokoušíme se odemknout již odemčený zámek, • nepokoušíme se zamknout již zamčený zámek, • na konci je zámek odemčený. Předpokládejme, že začínáme s odemčeným zámkem. Příklady slov, v nichž je manipulace se zámky v pořádku, jsou například ε, lfuog, gfg, glulguf, lu, glou, naopak podmínky nesplňují například slova uff, lluu, lufgl, glulgufu, ufo, lol, gl. Algoritmus musí vrátit true, pokud všechna slova akceptovaná automatem A pracují se zámky správně podle uvedených pravidel, v opačném případě musí vrátit false. Přesně popište princip fungování Vašeho algoritmu (nemusíte nutně použít pseudokód) a dokažte, že je tento algoritmus konvergentní (vždy skončí). Můžete využívat libovolné algoritmy z přednášky, pokud na to v textu patřičně upozorníte (nestačí však odkazovat se na dokázaná tvrzení, v jejichž důkazu není algoritmus). Požadovaná vlastnost správného zamykání zámku se na první pohled zdá být docela jednoduše popsatelná. Zásadní myšlenka je, že pokud bychom tuto vlastnost dokázali vyjádřit pomocí regulárního jazyka, mohli bychom následně kontrolu zvládnout za pomoci známých operací nad regulárními jazyky, respektive konečnými automaty. Cílem bude tedy vyjádřit jazyk všech slov se správným zamykáním a následně otestovat, zda je jazyk vstupního automatu podmnožinou tohoto jazyka. Náš hledaný jazyk by měl být nejobecnějším jazykem majícím požadovanou vlastnost v uvedené abecedě. To znamená, že bude obsahovat právě a jenom všechna možná slova se správným zamykáním zámku. Označme ho Llock ⊆ Σ∗. Zároveň by tento jazyk měl být regulární, aby se nám s ním dále dobře pracovalo. Llock bude velice užitečný proto, že náš algoritmus by měl vracet true právě tehdy, když L(A) ⊆ Llock, neboli L(A) \ Llock = ∅. Jak brzy uvidíme, Llock se nám bude hodit popsaný DFA M daným následujícím přechodovým grafem: qu ql f, o, g l f, o, g u Platí L(M) = Llock, protože automat M kontroluje právě podmínky zamykání, tedy akceptuje jakékoli slovo w ∈ Σ∗ takové, které je splňuje, žádné jiné podmínky na w neklade. S automatem M po ruce definujeme náš algoritmus následovně. Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi. IB102 úkol 7, příklad 1 Odevzdání: 5. 11. 2018 Jméno: UČO: list učo body Oblast strojově snímaných informací. Své učo a číslo listu vyplňte zleva dle vzoru číslic. Jinak do této oblasti nezasahujte. 1. Determinizujeme A podle algoritmu z přednášky 4, slide 8, A po determinizaci označme Adet . 2. Zkonstruujeme synchronní paralelní kompozici Adiff = Adet \ M podle algoritmu z přednášky 2, slide 11. • Postupujeme jako pro průnik, jen výsledná množina akceptujících stavů je F3 = F1×(Q2\ F2). Tedy Adiff akceptuje právě ve stavech, jejichž první složka odpovídá akceptujícímu stavu Adet a druhá složka neakceptujícímu stavu M. Tedy zjevně Adiff akceptuje právě slova, která Adet akceptuje a zároveň M zamítá. 3. V Adiff eliminujeme nedosažitelné stavy podle algoritmu z přednášky 4, slide 4. Dostáváme Adiff . 4. Nechť F je množina koncových stavů Adiff (t.j. F je množina dosažitelných koncových stavů Adiff ). 5. Vrátíme true, pokud F = ∅, jinak vrátíme false. Korektnost algoritmu vyplývá z toho, co bylo řečeno již na začátku. Víme, že L(M) = Llock, a jelikož determinizace je ekvivalentní úprava, rovněž platí L(Adet ) = L(A). Synchronní paralelní kompozice Adiff potom z definice akceptuje jazyk L(Adiff ) = L(Adet ) \ L(M) = L(A) \ Llock. Pokud ukážeme, že kompozice Adiff nemá žádný dosažitelný koncový stav, tedy F = ∅, z toho hned plyne, že L(A) \ Llock = ∅. To znamená, že L(A) nemůže obsahovat žádná slova porušující pravidla zamykání, protože taková slova by nebyla odstraněna odečtením Llock a náš algoritmus tedy vrátí korektně true. Pokud F = ∅, zjevně L(A) \ Llock = ∅, tedy v L(A) nutně existují slova, která porušují vlastnost zamykání zámku, protože jinak by byla i v Llock. Algoritmus tedy opět správně vrací false. Tím jsme dokázali korektnost. Náš algoritmus je konvergentní, protože algoritmy 1., 2. a 3. jsou konvergentní a naše práce s těmito algoritmy neobsahuje žádné cykly. Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.