\documentclass{ib102}
\usepackage[shorthands=off,czech]{babel}

% vim: spell spelllang=cs
% gen: ready

\assignment{7}
\exercise{1}
\points{2}
\duedate{5. 11. 2018}

%%% ZDE NAPISTE SVOJE UCO A JMENO
\name{}
\uco{}


\begin{document}
\begin{zadani}
Nechť $\Sigma = \set{ l, u, f, o, g }$. Navrhněte algoritmus, který pro zadaný NFA $\mathcal{A}$ pracující s abecedou $\Sigma$ zkontroluje zamykání zámku v jednotlivých slovech akceptovaných automatem $\mathcal{A}$. Kontrolu budeme provádět na slovech, v nichž $l$ představuje akci \uv{zamknout zámek} (\emph{lock}) a $u$ představuje akci \uv{odemknout zámek} (\emph{unlock}), písmena $f$, $g$ a $o$ představují akce, které na zámek nemají vliv.

\bigskip
\noindent Chceme kontrolovat, že
\begin{itemize}\itemsep0pt
\item po každém zamknutí dojde k odemknutí zámku,
\item nepokoušíme se odemknout již odemčený zámek,
\item nepokoušíme se zamknout již zamčený zámek,
\item na konci je zámek odemčený.
\end{itemize}

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 $\eps$, $lfuog$, $gfg$, $glulguf$, $lu$, $glou$, naopak podmínky nesplňují například slova $uff$, $lluu$, $lufgl$, $glulgufu$, $ufo$, $lol$, $gl$.
Algoritmus musí vrátit $\mathit{true}$, pokud všechna slova akceptovaná automatem $\mathcal{A}$ pracují se zámky správně podle uvedených pravidel, v opačném případě musí vrátit $\mathit{false}$.

\bigskip
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).
\end{zadani}

\begin{reseni}
%%% SEM PISTE SVE RESENI
\end{reseni}

\end{document}
