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).
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.