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

% vim: spell spelllang=cs

\assignment{10}
\exercise{2}
\points{0,5}
\duedate{6. 5. 2024 12:00}

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


\begin{document}
\begin{zadani}
    Mějme opět trpaslíčka pracujícího v dole z úlohy 0801. Trpaslíček má krumpáč, kterým těží rudu. Přijíždí za ním vozíčky, které on plní rudou a plné je posílá pryč. Naneštěstí se mu krumpáč může rozbít.

    Tentokrát se rozbilo i celé krumpáčové potrubí. Trpaslíček tedy musí rozbitý krumpáč posílat ve vozíčku do skladu krumpáčů. Když trpaslíčkům ve skladu s krumpáči přijede rozbitý krumpáč, pošlou další vozíček s novým krumpáčem. Od chvíle, kdy se trpaslíčkovi krumpáč rozbije, do chvíle, kdy dostane nový, nemůže odesílat vozíčky kromě vozíčku s krumpáčem.
    Trpaslíček je také svědomitý a na konci každé směny chce mít všechny vozíčky, které přijely, zase odeslané a krumpáč v pořádku.

    Zkonstruujte zásobníkový automat (PDA) pro jazyk, který popisuje možné posloupnosti akcí, které se trpaslíčkovi stanou za jeden pracovní den.

    \bigskip\noindent
    Stát se můžou následující akce: příjezd vozíčku ($p$), odjezd vozíčku ($o$), rozbití krumpáče ($b$), odjezd vozíčku s rozbitým krumpáčem ($or$) a příjezd vozíčku s novým krumpáčem ($pn$). Pozor, akce $or$ a $pn$ se skládají se dvou symbolů. Popisovaný jazyk $L$ je tedy nad abecedou $\Sigma = \set{p, o, b, r, n}$.

    \bigskip\noindent
	Dále musí platit:
	\begin{itemize}
		\item V žádnou chvíli nemůže odjet víc vozíčků, než kolik jich přijelo (pro každý prefix $u \in \Sigma^*$ nějakého slova z $L$ platí $\#_p(u) \geq \#_o(u)$).
        \item Na konci všechny vozíčky, které přijely, taky odjely (pro každé $w \in L$ platí $\#_p(w) = \#_o(w)$).
        \item Rozbít se může jen funkční krumpáč. Trpaslíček odešle rozbitý krumpáč poté, co se mu rozbil. Nový krumpáč dostane až poté, co odešle rozbitý. Jiné posloupnosti těchto akcí nemůžou nastat. Na začátku i na konci má trpaslíček k dispozici funkční krumpáč. (Pro libovolné $w \in L$ uvažme slovo $w_{brn}$, které vznikne z $w$ vynecháním $p$ a $o$. Platí $w_{brn} \in \set{brn}^*$.)
        \item Dokud má trpaslíček rozbitý krumpáč, vozíčky můžou přijíždět, ale může odjet pouze vozíček s rozbitým krumpáčem (mezi libovolným výskytem $b$ a k němu příslušejícím výskytem $n$ může být pouze jeden výskyt $o$, konkrétně $or$, můžou mezi nimi však být $p$).
        \item Rozbitý krumpáč může trpaslíček reportovat pouze odeslaním vozíčku s rozbitým krumpáčem. Nový krumpáč může dostat pouze v přicházejícím vozíčku. (Těsně před každým $r$ je znak $o$ a těsně před každým $n$ je znak $p$.)
	\end{itemize}

    Jazyk $L$ popisuje všechny možné sekvence akcí, které se během trpaslíčkova pracovního dne mohou stát. Tedy právě ty sekvence, které splňují výše popsané podmínky. V každém slově je vlevo nejstarší a vpravo nejnovější akce.

    \bigskip\noindent
	\begin{minipage}{0.49\textwidth}
		\noindent Příklady slov patřících do jazyka $L$:

		\medskip\noindent
		\begin{minipage}{0.45\textwidth}
			\begin{itemize}\itemsep0pt\parskip0pt
				\item $\varepsilon$
                \item $ppoopo$
                \item $pborpno$
			\end{itemize}
		\end{minipage}
		\begin{minipage}{0.5\textwidth}
			\begin{itemize}\itemsep0pt\parskip0pt
				\item $bporppnoo$
				\item $bporpnpborpnoo$
                \item $pbporpnoobporpno$
			\end{itemize}
		\end{minipage}
	\end{minipage}
	\hfill
	\begin{minipage}{0.49\textwidth}
		\noindent Příklady slov nepatřících do jazyka $L$:

		\medskip\noindent
		\begin{minipage}{0.5\textwidth}
			\begin{itemize}\itemsep0pt\parskip0pt
				\item $ppo$
				\item $poop$
				\item $brn$
			\end{itemize}
		\end{minipage}
		\begin{minipage}{0.45\textwidth}
			\begin{itemize}\itemsep0pt\parskip0pt
				\item $ppboropno$
				\item $pobororpnpnoo$
				\item $porpno$
			\end{itemize}
		\end{minipage}
	\end{minipage}

    \bigskip\noindent
	Uveďte \emph{zásobníkový automat}, který rozpoznává jazyk $L$.
	%včetně všech formálních náležitostí (nezapomeňte také explicitně uvést, jakým způsobem akceptuje).
	Výsledný zásobníkový automat \emph{nesmí} být rozšířený.
\end{zadani}

\begin{reseni}
	Úkol budete odevzdávat skrz AutomataTutor. Odkazy a informace k přihlášení jste
	dostali emailem. Potřebné údaje najdete i v interaktivní osnově v kapitole
	Softwarové nástroje.

	Pokyny ke konstrukci PDA najdete v stránce úkolu na webu AutomataTutor.

	Odevzdávaný zásobníkový automat si uložte. Pokud dojde k problémům se systémem
	AutomataTutor, požádáme vás o odevzdání výsledného zásobníkového automatu přes odevzdávárnu.
\end{reseni}

\end{document}
