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

% vim: spell spelllang=cs
% gen: ready

\assignment{12}
\exercise{1}
\points{0,5}
\duedate{23. 5. 2021 23:59}

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


\begin{document}
\begin{zadani}
Očkovací centrum má zřízený systém na registraci očkování. V tomto systému chceme kontrolovat platnost postupů při očkování, tedy toho, aby se pacient nejprve zaregistroval a poté  se buď odhlásil, nebo byl očkován -- nejprve první a poté druhou dávkou. Jedna registrace rezervuje termín pro první i druhou dávku. Tyto akce jsou v systému zaznamenány symboly:
\begin{itemize} \itemsep0pt
    \item $r$ $\ldots$ registrace pacienta na očkování
    \item $o$ $\ldots$ odhlášení pacienta z očkování
    \item $1$ $\ldots$ pacient obdrží první dávku
    \item $2$ $\ldots$ pacient obdrží druhou dávku
\end{itemize}
Slova nad abecedou $\Sigma = \set{r, o, 1, 2}$ pak představují sekvenci za sebou následujících akcí (čtenou klasicky zleva).

Uvažujme, že registrace je v daném prefixu slova platná, pokud není odhlášená ani ještě využitá, přičemž využitím registrace se myslí naočkování alespoň 1.\ dávkou.
Musí platit, že:
\begin{itemize}
    \item Registrovat se lze bez dalších omezení.
    \item Odhlásit se lze jen z dosud neodhlášené a nevyužité registrace (tedy před daným výskytem symbolu $o$ musí existovat platná registrace $r$, odhlásit se jde jen před první dávkou).
    \item Před očkováním první dávkou musí být pacient registrovaný, přičemž registrace nesmí být odhlášená ani již využitá (tedy existuje platná registrace $r$ před daným výskytem symbolu $1$).
    \item Před očkováním druhou dávkou musí být pacient již naočkován první dávkou.
\end{itemize}
Připomeňme, že na akce se díváme z pohledu očkovacího centra, je tedy možné libovolně prolínat očkování jedné osoby s dalšími registracemi, odhlašováními a očkováními.

\medskip
Sestrojte deterministický lineárně ohraničený automat (LBA) akceptující jazyk $L$ představující platné postupy očkování a jejich prefixy (tedy částečné postupy kdy ještě nebyla všechna očkování dokončena).\\
\noindent
Formálněji:
\begin{align*}
    &L' = \set{w \in \Sigma^* \mid (\#_{r}(w) - \#_{o}(w)) \geq \#_{1}(w) \geq \#_{2}(w)} \\
    &L = \set{w \in \Sigma^* \mid \text{každý prefix }w \text{ patří do jazyka } L'}
\end{align*}


Nejdříve slovně popište fungování LBA včetně popisu funkcionality jednotlivých stavů, poté ho zadefinujte i formálně.
\medskip

\noindent
Příklady slov, která patří do jazyka $L$: $\varepsilon$, $rrrr$, $r12$, $r1ro2$, $r1r2or$, $rr1or12$, $rr1$, $rorro1r2$.\\
Příklady slov, která nepatří do jazyka $L$: $r1r2o1$, $o$, $roo$, $r1or$, $r21$, $1r$, $2$.

\bigskip\noindent
\textit{Poznámka: Pokud píšete řešení v \TeX u, před odevzdáním prosím odmažte zadání. }
\end{zadani}

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